算法描述
快速排序采用了分治的思想：
- 分解：数组\(A[p\ldots r]\)被划分为两个子数组\(A[p\ldots q-1]\)和\(A[q+1\ldots r]\)，使得\(A[p\ldots q-1]\)中的元素小于等于\(A[q]\)，\(A[q+1\ldots r]\)中的元素大于等于\(A[q]\)
- 解决：通过递归调用快速排序，对子数组\(A[p\ldots q-1]\)和\(A[q+1\ldots r]\)进行排序
伪代码
在不同的快速排序算法实现中有不同的分区PARTITION策略
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
x = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1
算法复杂度
这里假设数组\(A[p\ldots r]\)中元素互不相同
- 最好情况：每次分区的时候，两边的分区大小一致，那么最多递归\(log(n)\)层，每一层都会比对\(n\)次，所以时间复杂度为\(\Theta(nlog(n))\)
- 最坏情况：每次分区选的主元\(A[q]\)都是当前数组中的最大值或者最小值，那么会递归\(n\)层，时间复杂度为\(\Theta(n^2)\)
- 平均情况：令随机变量\(X\)表示整个快速排序过程中比对次数，那么\(E(X)\approx 2nlnn\)，所以时间复杂度为\(\Theta(nlog(n))\)
期望\(E(X)\)的计算过程：
令随机变量
注意到，元素\(A[i]\)和\(A[j]\)最多只会发生一次比较（比较之后主元不会进入分区），所以
\[E(X)=E(\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{X_{ij}}}) \]同时\(A[i]\)与\(A[j]\)发生比较的概率，就是元素\(A[i]\)或者\(A[j]\)作为区间\(A[i\ldots j]\)中第一个被选取的主元，这一概率
\[Pr\{A[i]\,or\,A[j]\,as\,the\,first\,pivot\,chosen\,from\,A[i\ldots j]\}=\frac{2}{j-i+1} \]所以
\[\begin{align} E(X) &= E(\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{X_{ij}}})\\ &= \sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{E(X_{ij})}}\\ &= \sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{\frac{2}{j-i+1}}}\\ &= \sum_{i=1}^{n-1}{2(ln(n-i+2)-1)}\\ &= \sum_{i=1}^{n-1}{2(ln(i+2)-1)}\\ &\approx 2ln(n!)\\ &\approx 2nlnn\\ \end{align}\]