首页 > 代码库 > 【算法导论】学习笔记——第7章 快速排序
【算法导论】学习笔记——第7章 快速排序
对于包含n个数的输入数组来说，快速排序是一种最坏情况时间复杂度为theta(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，期望时间复杂度是theta(nlgn)，而且常数因子非常小，并可进行原址排序。
1. 快速排序的描述
快速排序可采用分治思想实现。
分解：数组A[p..r]被划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。
解决：通过递归调用快速排序，对数组A[p..q-1]和A[q+1..r]进行排序。
合并：因为子数组都是原址排序的，所以不需要合并操作，A[p..r]已经有序。
代码实现如下：
1 void swap(int A[], int i, int j) { 2 int tmp = A[i]; 3 A[i] = A[j]; 4 A[j] = tmp; 5 } 6 7 int Partition(int A[], int p, int r) { 8 int x = A[r]; 9 int i = p - 1, j;10 11 for (j=p; j<r; ++j) {12 if (A[j] <= x) {13 ++i;14 swap(A, i, j);15 }16 }17 swap(A, i+1, r);18 return i+1;19 }20 21 void QuickSort(int A[], int p, int r) {22 int q;23 24 if (p < r) {25 q = Partition(A, p, r);26 QuickSort(A, p, q-1);27 QuickSort(A, q+1, r);28 }29 }
Partition过程总是选择一个x=A[r]作为主元（Pivot Element），并围绕该元素花费子数组A[p..r]。显然，Partition的时间复杂度为theta(n)，n = r-p+1。
2. 快速排序的性能
最坏情况下，划分极不均匀，即划分为n-1与0，则T(n) = T(0) + T(n-1) + theta(n)，复杂度为theta(n^2)；最好情况下，划分足够均匀，即花费为floor(n/2)与ceil(n/2)-1，则T(n) = 2T(n/2) + theta(n)，复杂度为theta(nlgn)。通常，在划分比例为常数比例的情况下，复杂度均为theta(nlgn)。
证明：最坏情况下快速排序复杂度为theta(n^2)。
T(n) = max(T(q)+T(n-q-1)) + theta(n)，0<=q<=n-1，采用数学归纳法
<= max(c*q^2+c*(n-q-1)^2) + theta(n)，0<=q<=n-1
= c*max(q^2+(n-q-1)^2) + theta(n)
<= c*n^2 - c*(2n-1) + theta(n).
只要c*(2n-1)显著大于theta(n)，结论即成立。
7.2.5 证明：以划分比例1-a:a作递归树，因为0<a<=1/2，所以1-a>=a，设高度为h，所以当叶结点深度最小（即高度最小）满足(a^h)n = 1，解得h = -lgn/lga，同理，当叶结点深度最大（即高度最高）时，满足((1-a)^h) = 1，解得
h = -lgn/lg(1-a)。注意，在第k层划分后的数量一定为(a^x)*((1-a)(k-x))*，易知，划分后的最大数量比例为(1-a)^k，最小数量比例a^k。分别令将这两个比例*n为1，即可求解。
3. 快速排序的随机化版本
即采用随机抽样的随机化技术使得主元素随机选取，在等概率随机选取的情况下，期望运行时间为O(nlgn)。
代码如下：
1 void swap(int A[], int i, int j) { 2 int tmp = A[i]; 3 A[i] = A[j]; 4 A[j] = tmp; 5 } 6 7 int Partition(int A[], int p, int r) { 8 int x = A[r]; 9 int i = p - 1, j;10 11 for (j=p; j<r; ++j) {12 if (A[j] <= x) {13 ++i;14 swap(A, i, j);15 }16 }17 swap(A, i+1, r);18 return i+1;19 }20 21 int Randomized_Partition(int A[], int p, int r) {22 int n = r-p+1;23 int i = p+rand()%n, tmp;24 25 tmp = A[r];26 A[r] = A[i];27 A[i] = tmp;28 return Partition(A, p, r);29 }30 31 void QuickSort(int A[], int p, int r) {32 int q;33 34 if (p < r) {35 q = Randomized_Partition(A, p, r);36 QuickSort(A, p, q-1);37 QuickSort(A, q+1, r);38 }39 }
【算法导论】学习笔记——第7章 快速排序