快速排序的基本实现

快速排序算法是一种基于交换的高效的排序算法，它采用了 分治法 的思想：

1. 从数列中取出一个数作为基准数（枢轴，pivot）。
2. 将数组进行划分(partition)，将比基准数大的元素都移至枢轴右边，将小于等于基准数的元素都移至枢轴左边。
3. 再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素。

快排最重要的一步就是划分了。划分的过程用通俗的语言讲就是“挖坑”和“填坑”。

举个例子，首先给一组数组：

为了方便起见，我们选择第一个元素36作为基准数，这样就腾出了第一个位置（挖坑），下面首先自右向左寻找比基准数小的元素填至第一个位置（填坑）：

第七个位置被腾出，然后再自左向右寻找比基准元素大的元素填在空位处：

再重复上面的动作，直到第一趟划分完毕。此时[a0,a3]都是小于基准值a4的，[a5,a6]都是大于基准值a4的：

然后再对两个子序列递归地进行上述的过程，最终可得到有序序列。

总结一下这个划分的过程：

1. 设两个指示 i=left，j=right；设 arr[left] 为基准数
2. 从后向前寻找比基准元素大的元素，填至空位处
3. 从前向后寻找比基准元素小的元素，填至空位处
4. 重复执行 2、3 步，直到两指示相等，将基准元素填至指示的位置，本次划分结束

用代码表示为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int partition(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp = arr[left];
    while (i < j) {
        while (i < j && arr[j] > tmp)
            j--;
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < tmp)
            i++;
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = tmp;
    return i;
}
void quick_sort(int arr[], int left, int right) {
    if(left > right)
        return;
    int j = partition(arr, left, right);
    quick_sort(arr, left, j - 1);
    quick_sort(arr, j + 1, right);
}

当然用Haskell写是最简单的了:)

1
2
3
4
5
6

qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) =
    let s = qs $ filter (<= x) xs
        l = qs $ filter (> x)  xs
    in s ++ [x] ++ l

另一种实现划分的思路是先从左到右扫描一个比基准数大的元素，再从右到左扫描一个比基准数小的元素（左右两个指针 i、j 滑动），然后交换这两个元素，重复操作直到两指针相遇，然后将基准元素 arr[left] 与左子序列最后的元素 arr[j] 进行交换即可，用代码描述为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int partition(int arr[], int left, int right) {
    int i = left, j = right + 1;
    int temp = arr[left];
    while (true) {
        while (arr[i] < temp && i < right) {
            i++;
        }
        while (arr[j] > temp && j < left) {
            j++
        }
        if (i >= j)
            break;
        swap(arr[i], arr[j]);
    }
    swap(arr[left], arr[j]);
    return j;
}

快速排序算法的平均时间复杂度为 $O(NlogN)$。快排的最差情况为序列完全有序，此时快排退化为冒泡排序，时间复杂度为 $O(n^2)$ 。

快速排序的改进和优化

快速排序也有不足之处，比如对于元素较少或接近有序的数组来说，快速排序平均性能比插入排序差。这是因为小数组信息熵相对来说比较小（特别是经过一系列的快速排序调用以后），而插入排序在数据接近有序的情况下时间复杂度接近 $O(N)$，再加上快速排序递归调用也会有一些性能损耗。因此，针对小数组，我们可以加个判断，对小数组使用插入排序。Java标准库自带的排序DualPivotQuicksort就是这么干的，INSERTION_SORT_THRESHOLD = 47。

另外一个改进快速排序性能的方法就是使用 双枢轴，即将数组三切分(大于枢轴，等于枢轴，小于枢轴），可以证明这样是熵最优的并且更高效。为什么这样划分呢？因为统计表明对大规模数组进行排序时，数据重复的情况比较多，因此使用双枢轴可以有效避免相等元素之间的比较。以 Java 标准库为例，JDK 1.8 中的 DualPivotQuicksort 实现了一种 快速三向切分 的快速排序，它通过将相等元素聚集起来的方式使熵最优（原理：将相等元素聚集起来，不必再切分这些元素）。

还有一个优化的杀手锏就是 改进划分的策略，这里 DualPivotQuicksort 使用了一种称为 五取样划分 的策略对数组进行划分，类似于 BFPRT 算法。

总结一下，快排的改进主要有三种方法：小数组使用插入排序、双枢轴（快速三向切分）、划分策略优化（五取样划分）。经过优化后的快速排序算法时间复杂度可以介于 $O(N)$ 到 $O(NlogN)$ 之间，性能更优。具体实现可以看 DualPivotQuicksort 的源码，实现的很复杂，非常奇妙。