内存排序(四)——快速排序

核心过程

从原数组里选一个数a(通常是第一个)，然后调整数组。
达到数组里所有比a小的数都在a的左边，反之在右边。
比如[4, 1, 3, 5, 2]，a = 4,一轮后可能会变成[2,1,3,4,5]，a左边的都比a小，反之比a大。
很多人讲快排都纠结这个核心过程的指针怎么移动，忽略了快排真正的意义其实在迭代过程。
意图讲明白了，加上代码一看就懂。

public static int quickSortCore(int[] list, int begin, int end){
    /**
     * 基准值下标暂存
     */
    int temp = begin;
    while(begin < end) {
        /**
         * 这两个while的顺序依赖于基准值的取法
         * temp取的begin就是现在这样
         * 如果temp取的end两个while要交换顺序
         */
        while(begin < end && list[end] >= list[temp]) {
            --end;
        }
        while(begin < end && list[begin] <= list[temp]) {
            ++begin;
        }
        swap(list, begin, end);
    }
    swap(list, temp, begin);
    return begin;
}

private static void swap(int[] list, int left, int right){
    int temp = list[left];
    list[left] = list[right];
    list[right] = temp;
}

迭代过程

这也是开始和前面方法有区别的地方，但是同样在归并里一样会看到这样的迭代过程。
由核心过程中的数a，将数组分为了左右两个部分(两部分都不包含a，也就是去掉a剩下的的左右两边)
那么对两边分别做同样的核心过程即可。这个迭代过程实现了"分治"的效果。
让快排根本上区别于之前的比较排序。归并同样是类似的原理。
当然快排有不“稳定”的情况，但这个内容不属于本系列的目的。

public static void quickSortIteration(int[] list, int begin, int end){
    if(begin >= end)
        return;
    int mid = quickSortCore(list, begin, end);
    quickSortIteration(list, begin, mid - 1);
    quickSortIteration(list, mid + 1, end);
}