1 前言
快速排序算法是一类有效的排序算法，平均花费O(nlogn)的比较操作和O(1)的空间进行排序。但是快速排序算法存在花费O($n^2$)的较差情况出现，这种情况在之后会提到，这种情况即输入数组有序。经典快速排序算法出现这种较差情况的原因是输入数组的性质，而随机快速排序则解决了花费比较操作数依赖于输入的问题，使得较差情况的出现成为一个随机事件，这一随机事件发生的概率其实也非常低。随机快速排序期望操作数在O(nlogn)。
本文包括快速排序，随即快速排序的简单介绍以及对随即快速排序性能的详细证明。
2 快速排序
比如输入input=(5,3,7,6,2)，进行快速排序。首先选定一个基准（pivot)，一般使用第一个元素作为基准，pivot=5。
快速排序设置两个“指针”，分别在最左端和最右端，这里指向5和2。开始时，从最右端的指针开始，判断右“指针”指向元素是否比pivot小，若小则停止，将右“指针”的值写入左“指针”的位置，然后切换至左“指针”；若大，则继续向左移动。与之对应，左“指针”向相反方向移动，判断左“指针”指向元素是否比pivot大，若大则将值写入右“指针”处。具体如下图所示（红色的5为pivot）。
一轮操作之后，pivot=5将数组分割成左右两部分，左边均小于5，右边均大于5。之后分别对分割出的部分都进行上述操作，即先选择pivot，再分割。直到每一部分都仅有一个元素时，终止程序，返回序列。程序使用递归实现。
容易看出，当数组input有序，需要O($n^2$)个比较操作。
3 随机快速排序
随机快速排序算法核心在于pivot选择上的随机性。每次选择pivot的时候，均在该部分的所有元素当中均匀随机的选择，每个元素被选择成为pivot的概率相等。
下面证明随机快速排序期望比较操作次数为$2nlnn+\Omicron(n)$。
设输入$input=x=(x_1,x_2,…,x_n)$,令$y=(y_1,y_2,…,y_n)$是$x$的递增形式，即$y$就是$x$按递增排序之后的结果。定义随机变量$X$，对$\forall i<j$ ，若$y_i,y_j$在整个随即快速排序程序运行过程当中进行了比较，那么$X_{ij}=1$；否则$X_{ij}=0$。很容易看出$X_{ij}$服从伯努利分布，也就是0-1分布。
让我们思考什么时候会产生比较，两个元素进行比较，当且仅当其中一个元素是基准pivot。那么很显然，两个元素仅可能进行至多一次比较。那么总的比较操作数可以写作如下形式。
根据期望的运算法则，$E(X+Y)=E(X)+E(Y)$，还有伯努利分布的期望性质$E(X)=Pr(X=1)$可以得到，
现在需要计算$y_i$和$y_j$有多大概率进行比较操作。设$Y_{ij}=\{ y_i,y_{i+1},…,y_{j-1},y_j \}$，这个集合显然是递增的，因为它是$y$截取的一部分。回顾快速排序，选择基准pivot之后，我们会将原有的区间一份为二，以pivot为界。$y_i$和$y_j$起始在同一个区间，这个区间就是$x$整体。一轮操作之后，$y_i$和$y_j$有三种可能，第一种是仍然在同一区间，第二种是所处两个不同的区间（被分割了），第三种是$y_i$和$y_j$其中一个元素在刚才成为了pivot，之后不会再对成为pivot的元素操作了。从另一个角度看，$y_i$和$y_j$要么进行比较，要么没有进行比较，第二情况对应了没有进行比较，第三种情况对应了进行比较，而第一种情况在这个角度来看没有意义。考虑，什么时候会出现第二种和第三种情况？显然，当这一轮操作选择$pivot\in\{y_{i+1},y_{i+2},…,y_{j-1}\}$时，会出现第二种情况；当$pivot=y_i或y_j$会出现第三种情况。
根据上述分析，又因为是均匀随机采样，概率取决于数量，那么可以得到，
如此，可以得到，
$\sum_{k=1}^{\infty}\frac{1}{k}$是调和级数。$\sum_{k=1}^{n}\frac{1}{k}$能够证明其范围在$ln(n+1)$和$lnn+1$之间，更具体的能够证明其极限收敛至$lnn+\gamma$，常数项为欧拉-马歇罗尼常数。具体证明可以自行搜索，这里仅用结论。
于是得到了$E(X)=2nln+\Omicron(1)$，而$E(X)$之前提到即为程序期望的比较操作数。
由于排序时间开销主要由比较操作决定，因此我们得到了随即快速排序算法的性能估计。
By BRB
文章借鉴 Probability and Computing Randomized Algorithms and Probabilistic Analysis