首页 > 代码库 > Chapter 7 快速排序
Chapter 7 快速排序
快速排序---实际排序应用中最好的选择
期望时间复杂度为θ(nlgn)最坏情况复杂度为θ(n2)----由于隐含常数因子小及原址排序，故广泛用
7.1 快速排序描述
采用分治思想
分解：将数组A[p..r]划分为两个子数组A[p..q-1]和A[q+1,r]，划分的依据是使A[p..q-1]的值全都小于或等于A[q]，A[q+1..r]的每个值都大于等于A[q]
解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序
合并：由于子数组都是原址排序，所以无需合并便已有序
核心思想：数组中找个"坑"，将小于等于该坑的值扔坑的左边，大于等于该坑的值扔坑的右边，在每次递归采取同样措施(自然每次递归都要选坑)
数组的划分(1.其中的r也在数组内,因此在测试代码时为array.count-1 2.其中选择的坑为数组最末元素)：
static int Partition(List<int> array,int p,int r) { int x = array[r], temp; int i = p-1; //类似于一个指示,在该指示左边的值均小于x for(int j=p;j<r;j++) { if(array[j]<=x) //遇到比x小的,放到i的下一位去 { i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } array[r] = array[i + 1]; array[i + 1] = x; return i + 1; }
快速排序：
static void QuickSort(List<int> array,int p,int r) { int q; if(p<r) //进行递归的条件 { q = Partition(array, p, r); QuickSort(array, p, q - 1); QuickSort(array, q + 1, r); } }
7.2 性能分析
最坏情况(基本不可能出现)：每次划分子问题时(包括递归中)产生子问题包含n-1和0个元素，则时间复杂度为θ(n2)
最好和平衡划分的情况(即任何一种常数比例的划分)：产生的递归树深度为θ(lgn)，每一层的时间代价都是O(n),从而可知算法的运行时间是θ(nlgn)
7.3 快速排序的随机化版本(即在选择"坑"时，随机选取)
static int RandomPartition(List<int> array,int p,int r) { Random rnd = new Random(); int position = rnd.Next(p, r + 1); //随机产生一个p..r之间的数,代表选取"坑"的下标 int temp = array[r]; //将选取的array[position]与array[r]交换 array[r] = array[position]; array[position] = temp; return Partition(array, p, r); }
--------练习--------
7.4-1 证明在递归式 T(n)=max0≤q≤n-1(T(q)+T(n-q-1))+θ(n) 中, T(n)=Ω(n2)
思路,代入法 即证 cn2≤max0≤q≤n-1(T(q)+T(n-q-1))+θ(n)
由 max0≤q≤n-1(T(q)+T(n-q-1))+θ(n)≥max(q2+(n-q-1)2)+θ(n)≥(n-q-1)2+θ(n)
∴ T(n)≥(n-q-1)2+θ(n)≥cn2
--------------------
Chapter 7 快速排序