快速排序

快速排序（quick sort）同样是分治策略的一种体现，它的思想为将序列分为两个子序列，且前一个子序列的数都不大于后一个子序列，在子序列分别递归地排序之后，原序列自然有序。

由此可见，归并排序的计算量和难点在于合，而快速排序在于分。

要实现以上所述的那种子序列的划分，其关键在于寻找轴点（pivot），轴点左侧的元素均不比它更大，轴点右侧的元素均不比它更小。

显然，轴点必定已然就位。但坏消息是，在原始序列中，轴点未必存在。比如，在乱排（derangement）序列中，轴点就不存在。特别地，在有序序列中，所有元素皆为轴点，反之亦然。从这个角度来看，所谓的快速排序无非就是将所有元素逐个转换为轴点的过程。具体来说，通过适当交换，可使任一元素转换为轴点。

任何一个有序序列只要经过一次循环移位就可得到一个乱排序列，比如 [2, 3, 4, ..., n, 1]。

def partition(lis):
    pivot = lis[0]
    mi = 0
    for k in range(1, len(lis)+1):
        if lis[k] < pivot:
            mi += 1
            lis[mi], lis[k] = lis[k], lis[mi]
    lis[0], lis[mi] = lis[mi], lis[0]
    return mi


def quicksort(lis):
    if len(lis) < 2:  # 单元素区间自然有序，否则...
        return lis
    mi = partition(lis)  # 先构造轴点，再
    quicksort(lis[:mi])  # 对前半段排序
    quicksort(lis[mi:])  # 对后半段排序


# 测试
lis = [4, 3, 8, 7, 1, 9, 6]
print(quicksort(lis))  # [1, 3, 4, 6, 7, 8, 9]

快速排序是不稳定（unstable）的，lo/hi 的移动方向相反，左/右侧的大/小重复元素可能前/后颠倒。

快速排序是就地（in-place）的，只需 \(O(1)\) 的附加空间。

最好情况下，每次划分都（接近）平均，轴点总是（接近）中央，此时时间复杂度为 \(O(nlogn)\)。

最坏情况下，每次划分都极不均衡，比如，轴点总是最小或最大元素，此时时间复杂度为 \(O(n^2)\)，与冒泡排序相当！即便采用随机选取、（Unix）三者取中之类的策略，也只能降低最坏情况的概率，而无法杜绝。

随机选取：不再是每次都固定的将首元素作为候选轴点，而是在整个序列中，随机的选择其一。

三者取中：每次都是在整个序列中，随机的抽取三个元素，然后将其中数值居中的那个作为候选轴点。

以均匀独立分布为例，在平均情况下，其时间复杂度为 \(O(nlogn)\)，特别的，\(n\) 约等于 1.39。