【算法】快速排序

class Solution {
    /**
     * 快速排序
     * @param A
     */
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    // 将 array 数组中 start 到 end 之间的元素进行排序
    private void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            // start 如果等于 end, 说明就一个元素, 不用排序
            // start 正常情况下不会大于 end
            return;
        }
        // 设置两个指针, 分别指向头尾
        int left = start, right = end;
        // 1. 分割操作第一步 : 取中心点
        // 取中心点, 一般取 start 与 end 索引的中心索引对应的数组元素值
        // 如下取中间值是强行指定的, 也可以随机指定 , 指定 start 与 end 之间的一个随机值
        // 尽量不选取 start 和 end 索引的值
        int pivot = array[(start + end) / 2];
        // 2. 分割操作第二部 : 进行数组元素分割
        // 注意此处, left 小于等于 right , 不能是小于
        while (left <= right) {
            // 找到一个不属于左边部分的元素, 将其交换到右边
            while (left <= right && array[left] < pivot) {
                // 如果遇到一个元素不属于左边, 则退出循环
                left++;
            }
            // 找到一个不属于右边部分的元素, 将其交换到左边
            while (left <= right && array[right] > pivot) {
                // 如果遇到一个元素不属于右边, 则退出循环
                right--;
            }
            // 交换上述检测出来的需要交换的元素
            if (left <= right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;
                // 交换完毕后, 继续向后遍历
                left++;
                right--;
            }
            // 交换完毕后, 继续循环, 该循环退出的条件是 left >= right
        }
        // 分割完毕后, 继续递归
        // 如果按照中心点分割完毕的话, 上面的循环退出, left >= right
        // 索引的分布如下 : start , right, left, end
        quickSort(array, start, right);
        quickSort(array, left, end);
    }
}