Preview
这里主要讲快速排序的代码，证明，不同版本以及分析。最后会写一点关于归并排序、堆排序和快速排序的一点感想。这一章相对来说比较简单，知识点的把握没有什么难度。
Keywords: 分治法 期望运行时间
算法介绍
快速排序的思路与归并排序非常接近。归并排序讲究先分再治，而快速排序将目标数组先 分解 为两个子数组，并保证一个子数组中的所有的值都小于等于另一个子数组中的任何一个值。注意，将原数组划分为两个子数组不需要规定子数组的大小，但要计算用来分割的下标。接着快排递归调用来 解决 剩下的排序。由于快排是原址排序，所以 合并 部分不需要像归并排序那样复杂。
只有遵循上述的 分解、解决、合并 操作的排序才是快速排序。我们可以敏锐地发现，不同于能够在线性时间内构造有顺序的（尽管不是严格顺序的）堆排序，快速排序和归并排序的构造顺序依赖于分治法，而每分解一步就治理一步的特点又把快排和归并区别开来。
代码与证明
我们以从小到大排序为例：
QUICKSORT(A,p,r)//p,r的初始值是1和A.length
if p<r
q = PARTITION(A,p,r)//将数组分割，让元素们站好队，并返回pivot
QUICKSORT(A,p,q - 1)
QUICKSORT(A,q +1, r)
计算PARTITION：
PARTITION(A,p,r)
x = A[r]//将A[r]作为一个pivot
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]//比pivot小的元素放到左边
exchange A[i + 1] with A[r]//pivot放到比自己小的那一堆的元素们的刚好右边
return i +1
有意思的是，指针 j 将遍历录入数组从左到右的下标（除了被选为pivot的A[r]），而指针 i 所指向的下标负责接收储存下一个被判定为「比pivot还小」的值。显然地，在 j 遍历的过程中，我们对 j 右边的数字们是不感兴趣的，而 i 左边的数字们是必须有「比pivot还小」的义务。因此，我们把以下性质当作循环不变量：
每一次循环开始时，对于任意一个值「k」，有：
- 若 p <= k <= i ，则A[k] <= x
- 若 i+1 <= k <= j - 1 ，则A[k] > x
- 若 k = r ，则A[k] = x
对于这三点，我们仍然可以利用数学归纳法来证明它们的正确性。证明过程依然分为 初始化 、 保持 、 终止 三个部分。具体过程比较简单就略过了。以上我们就证明了快速排序的正确性。
随机化版本
用非固定的下标来控制的快速排序在稳定性方面总是让我们联想到插入排序。插入排序典型的矛盾在于，对于一个逆有序数组，插入排序所消耗的时间必然是Θ(n^2)。快速排序也存在类似的矛盾，有序数组的劣质pivot会导致每次遍历一遍都找不出比pivot还小的元素，并且让这时候的快排看起来像插入排序的一种特殊情况，耗时还是Θ(n^2)——尤其是当实际情况很有可能出现有序数组，比如对一个储存最小堆的数组使用从小到大的快速排序的时候。现在我们可以考虑利用随机抽样来降低实际情况中出现有序排列的可能性。
RANDOMIZED-QUICKSORT(A,p,r)
i = RANDOM(p,r)
exchange A[r] with A[i]
return PARTITION(A,p,r)
另外的两个算法只需要做微小的改动，在此不表。其他具体的分析我们将稍后讲解。
性能分析
正如我们在「随机化版本」中提到的那样，快速排序的成王败寇取决于录入的数组。分割得到的两个子问题的规模和应当为「n-1」。当我们意在从小到大快速排序数组的时候，假设每次都找不到比pivot小的数字，即两个子问题分别包含n-1和0个元素时，快速排序的最坏情况发生了（证明过程略）。我们可以很容易地得到递归式的耗时：
T(n) = T(n - 1) + T(0) + Θ(n) = T(n - 1) +Θ(n)
利用代入法可以得到解为 T(n) = Θ(n^2)。因此我们得到结论：对于一个近似有序的数组，使用快速排序所消耗的时间为Θ(n^2)，同比之下插入排序所消耗的时间甚至为Θ(n)。
显然最好的情况是，每次pivot分割后，两个子数组的大小均不超过「n/2」，也就是真实意义上的平均划分——如果我们忽略「俩子问题规模和应当在n的基础上减1」的话——这样递归式为 ` T(n) = 2T(n/2) + Θ(n) ` ， 而且求得的解应该为Θ(nlogn)。
对于平均情况，讲解有点麻烦就不说了。只需要知道只要划分是常数比例的话，算法的运行时间仍然是O(nlogn)。
对于常数1:9的情况下的快速排序的递归树
现在不妨考虑更高级的随机快排。显然地，随机快排的最坏情况也逃脱不了O(n^2)的命运，但它的「期望运行时间」可以达到O(nlogn)。RANDOM方法规定在选择pivot的时候，一旦某个元素被选择了pivot，之后它将不会再次被选为pivot，这和普通的快排是一样的，也就是说PARTITION的调用总次数为 n 次，而且每一对元素比且仅比一次。
接着我们定义两件事情。第一件是数组的各个元素为z1, z2, …, zn，其中zi为第i小的元素。第二件是定义一个指示器随机变量Xij = I{zi与zj进行比较}，值只分为0和1两种，j>i，Zij指zi到zj的集合。剩下的计算见图：
最后我们得到了随机快速排序的期望运行时间为O(nlogn)。
Ω/Θ(nlogn)的思考
我们已经学完了归并排序，堆排序和快速排序。这三大排序应该是八大排序中最常见、最常用也是最好用的三个排序了。显然，堆排序依赖于「一分为二」的堆结构，而快排和堆排依赖于分治法（堆排其实是选择类排序，快排属于交换类排序，只有归并排序是归并类排序）。这种「一分为二」的优势让它们与其他普通排序区别开来（不过并不是说就这三种是一分为二了……每年都会有大佬写出新的排序方法的）。那么一分为多是否会把nlogn的极限提高呢？对于归并排序，我们已经得出过一分为多的通用递归式, 而堆排序似乎也可以依赖类似三叉堆这样的结构来实现一分为三（遗憾的是快速排序似乎并没有办法改造）。在排序前如果能够选择足够优秀的那个「多」，也应该能大幅度减少排序所消耗的时间。不过这太难了……在此不表。实际应用中似乎更偏向「多路归并排序」这样的东西，所以算法导论上也几乎没有提到过一分为多（毕竟只是导论）。
还是只讨论一分为二。定理 在最坏的情况下，任何比较排序算法都需要做Ω(nlogn)次比较。 告诉了我们最坏情况的下界（证明在下章）。如果我们想要依赖一分为二的思想写一个新的算法，就不要对突破nlogn抱有希望了。
最后附上快速排序的typescript的实例代码 （Author: Robin）
最近要实习，估计更新速度要慢很多了……