快速排序的另一种简单写法

最近在看TCPL，第四章的函数与程序结构里面有一个快速排序的例子，并且几句话就把快速排序总结了，非常精炼。快速排序利用的是分治的思想(Divide Conquer)，理解了分治，就能理解快排。这里记录一下，并且讲解一下程序的原理。

对于一个给定的数组，从中选择一个元素，以该元素为界将其余元素划分为两个子集，一个子集中的所有元素都小于该元素，另一个子集中的元素都大于或等于该元素。对这两个子集递归执行这一过程当子集中的元素小于2时，这个子集就不需要再次排序，终止递归。

static void sortRecursively(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = (left + right)/2;
    swap(arr, left, pivot);
    int last = left;
    for (int i = left + 1; i <= right; i++) {
        if (arr[left] > arr[i]) {
            swap(arr, ++last, i);
        }
    }
    swap(arr, left, last);
    sortRecursively(arr, left, last - 1);
    sortRecursively(arr, last + 1, right);
}
    

其中交换数组元素的代码被抽取出来：

static void swap(int[] arr, int k, int j) {
    int tmp = arr[k];
    arr[k] = arr[j];
    arr[j] = tmp;
}

首先选取枢纽点，这里选取的是元素中心位置，然后交换到最左侧的left，这样做的目的便于后面双指针的移动。

quick_sort1

交换后并定义last指针指向left位置，这里的last指针表示last之前并且包括last的元素都小于枢纽元素pivot。

quick_sort1

之后便开始通过对比枢纽元素与枢纽元素后面的元素，将小于枢纽元素的元素交换到前面，并移动last指针，由于24与67都比23大，所以last就保持不变，也没有任何交换的操作。

quick_sort1

当遇到i移动到3的时候，便交换24与3，并且移动last指针指向3。

quick_sort1

之后继续移动i，直到最后一个元素。这样，last之前的元素都小于枢纽元素，last之后的元素都大于等于枢纽元素。

quick_sort1 quick_sort1

然后再恢复划分的子集，让枢纽元素之前的子集和枢纽元素之后的子集分别递归调用排序，递归的终止条件就是子集只有一个元素的时候，这时子集当然是有序的。这样就完成了对整个数组的排序。

对于快速排序排序还有一些复杂的细节，比如枢纽元素的选择等。关于时间复杂度与空间复杂度的分析可以参考维基百科。