快速排序算法分析及程序示例

实例说明：

　　用快速排序的方法对数组进行排序。


实例解析：

　　快速排序 (QuickSort)

　　快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法（Divide-and-ConquerMethod）。

　　（1）分治法的基本思想，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

　　（2）快速排序的基本思想

　　设当前待排序的无序区为 R[low..high], 利用分治法的基本思想如下：

　　① 分解。在 R[low..high] 中任选一个记录作为基准（pivot），以此基准将当前无序区划分为左、右两个较小的子区间 R[low..pivotpos-1] 和 R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录（不妨记为 pivot）的关键字 pivot.key，右边的子区间中所有记录的关键字均大于等于 pivot.key，而基准记录 pivot 则位于正确的位置（pivotpos）上，无需参加后续的排序。

　　划分的关键是要求出基准记录所在的位置 pivotpos。划分的结果可以简单地表示为（注意 pivot=R[pivotpos]）：R[low..pivotpos-1].keys<=R[pivotpos].key<=R[pivotpos+1..high].keys，其中 low<=pivotpos<=high。

　　② 求解。通过递归调用快速排序对左、右子区间 R[low..pivotpos-1] 和 R[pivotpos+1..high] 快速排序。

　　③ 组合。因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，“组合”步骤无需做什么，可看作是空操作。

快速排序算法

void QuickSort(SeqList R,int low,int high){ 　 // 对 R[low..high] 快速排序
　　int pivotpos;　　　　　　　　　　　　　　　　 // 划分后的基准记录的位置
　　if(low<high){ 　　　　　　　　　　　　　　　 // 仅当区间长度大于 1 时才须排序
　　　　pivotpos=Partition(R,low,high); 　　　　// 对 R[low..high] 做划分
　　　　QuickSort(R,low,pivotpos-1);　　　　　　// 对左区间递归排序
　　　　QuickSort(R,pivotpos+1,high); 　　　　　// 对右区间递归排序
　　}
}//QuickSort

　　为排序整个文件，调用 QuickSort(R,1,n) 即可完成对 R[1..n] 的排序。


划分算法 (Partition)

　　第 1 步，（初始化）设置两个指针 i 和 j,它们的初值分别为区间的下界和上界 , 即 i=low，j=high；选取无序区的第一个记录 R[i]( 即 R[low] ) 作为基准记录，并将它保存在变量 pivot 中。

　　第 2 步，令 j 自 high 起向左扫描，直到找到第 1 个关键字小于 pivot.key 的记录 R[j], 将 R[j] 移至 i 所指的位置上，这相当于 R[j] 和基准 R[i]( 即 pivot) 进行了交换，使关键字小于基准关键字 pivot.key 的记录移到了基准的左边，交换后 R[j] 中相当于是 pivot；然后令 i 指针自 i+1 位置开始向右扫描，直至找到第 1 个关键字大于 pivot.key 的记录 R[i] ，将 R[i] 移到 i 所指的位置上，这相当于交换了 R[i] 和基准 R[j]，使关键字大于基准关键字的记录移到了基准的右边，交换后 R[i] 中又相当于存放了 pivot；接着令指针 j 自位置 j-1 开始向左扫描，如此交替改变扫描方向，从两端各自往中间靠扰，直至 i=j 时，i 便是基准 pivot 最终的位置，将 pivot 放在此位置上就完成了一次划分。

划分算法如下所示：

int Partition(SeqList R,int i,int j){
　　//调用 Partition(R,low,high)时,对R[low..high]做划分，并返回基准记录的位置
　　ReceType pivot=R[i];　　　　// 用区间的第 1 个记录作为基础
　　while(i<j){　　　　　　　　 // 从区间两端交替向中间扫描，直至 i=j 为止
　　　　while(i<j && R[j].key>=pivot.key)　　//pivot 相当于在位置 i 上
　　　　　　j--;　　　　　　　　// 从右向左扫描，查找第 1 个关键字小于 pivot.key 的记录 R[j]
　　　　if(i<j)　　　　　　　　 // 表示找到的 R[j] 的关键字小于 pivot.key
　　　　　　R[i++]=R[j];　　　 // 相当于交换 R[i] 和 R[j], 交换后 i 指针加 1
　　　　while(i<j && R[i].key<=pivot.key)　　　　//pivot 相当于在位置 j 上
　　　　　　i++;　　　　　　　　// 从左向右扫描，查找第 1 个关键字大于 pivot.key 的记录 R[i]
　　　　if(i<j)　　　　　　　　 // 表示找到了 R[i], 使 R[i].key>pivot.key
　　　　　　R[j--]=R[i];　　　 // 相当于交换 R[i] 和 R[j], 交换后 j 指针减 1
　　}//endwhile
　　R[i]=pivot;　　　　　　　　// 基准记录已被最后定位
　　return i;
}//Partition


程序代码—快速排序

#include <stdio.h>
#define MAX 255
int R[MAX];
int Partition(int i,int j){
　　/*调用 Partition(R,low,high)时,对R[low..high]做划分,并返回基准记录的位置*/
　　int pivot=R[i];　　　　　　/* 用区间的第 1 条记录作为基准 */
　　while(i<j){　　　　　　　　/* 从区间两端交替向中间扫描，直至 i=j 为止 */
　　　　while(i<j && R[j]>=pivot)　　　　/*pivot 相当于在位置 i 上 */
　　　　　　j--;　　　　　　　　/* 从右向左扫描，查找第 1 个关键字小于 pivot.key 的记录 */
　　　　if(i<j)　　　　　　　　 /* 表示找到的 R[j] 的关键字小于 pivot.key*/
　　　　　　R[i++]=R[j];　　　　/* 相当于交换 R[i] 和 R[j], 交换后 i 指针加 1*/
　　　　while(i<j && R[i]<=pivot)　　　　/*pivot 相当于在位置 j 上 */
　　　　　　i++;　　　　　　　　/*从左向右扫描，查找第 1 个关键字大于 pivot.key 的记录 R[i] */
　　　　if(i<j)　　　　　　　　 /* 表示找到了 R[i], 使 R[i].key>pivot.key*/
　　　　　　R[j--]=R[i];　　　 /* 相当于交换 R[i] 和 R[j], 交换后 j 指针减 1*/
　　}/*endwhile*/
　　R[i]=pivot;　　　　　　　　/* 基准记录已被最后定位 */
　　return i;
}/*end of partition*/

void Quick_Sort(int low,int high){　　　/* 对 R[low..high] 快速排序 */
　　int pivotpos;　　　　　　　　　　　　/* 划分后的基准记录的位置 */
　　if(low<high){　　　　　　　　　　　　/* 仅当区间长度大于 1 时才需排序 */
　　　　pivotpos=Partition(low,high); 　/* 对 R[low..high] 做划分 */
　　　　Quick_Sort(low,pivotpos-1); 　　/* 对左区间递归排序 */
　　　　Quick_Sort(pivotpos+1,high);　　/* 对右区间递归排序 */
　　}
}/*end of Quick_Sort*/

void main(){
　　int i,n;
　　clrscr();
　　puts("Please input element number of the sequence:");
　　scanf("%d",&n);
　　if(n<=0 || n>MAX){
　　　　printf("n must more than 0 and less than %d.\n",MAX);
　　　　exit(0);
　　}
　　puts("Please input the elements one by one:");
　　for(i=1;i<=n;i++)
　　　　scanf("%d",&R[i]);
　　puts("The sequence you input is:");
　　for(i=1;i<=n;i++)
　　　　printf("%4d",R[i]);
　　Quick_Sort(1,n);
　　puts("\nThe sequence after quick_sort is:");
　　for(i=1;i<=n;i++)
　　　　printf("%4d",R[i]);
　　puts("\n Press any key to quit..");
　　getch();
}


归纳注释

　　快速排序的时间主要耗费在划分操作上，对长度为 k 的区间进行划分，共需 k-1 次关键字的比较。

　　最坏时间复杂度：最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做 n-1 次划分，第 i 次划分开始时区间长度为 n-i-1, 所需的比较次数为 n-i(1<=i<=n-1), 故总的比较次数达到最大值 Cmax =n(n-1)/2=O(n^2) 。如果按上面给出的划分算法，每次取当前无序区的第 1 个记录为基准，那么当文件的记录已按递增序（或递减序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。

　　最好时间复杂度：在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果与基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为 O(n×lgn)。

　　用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为 O(lgn), 而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过 n，故整个排序过程所需要的关键字比较总次数 C(n)=O(n×lgn) 。因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 O(n^2 )，最好时间复杂度为 O(n×lgn)。

　　基准关键字的选取：在当前无序区中选取划分的基准关键字是决定算法性能的关键。 ① “三者取中”的规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，以三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区的第 1 个记录进行交换，此后的划分过程与上面所给的 Partition 算法完全相同。 ② 取位于 low 和 high 之间的随机数 k(low<=k<=high), 用 R[k] 作为基准；选取基准最好的方法是用一个随机函数产生一个位于 low 和 high 之间的随机数 k(low<=k<=high), 用 R[k] 作为基准 , 这相当于强迫 R[low..high] 中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。随机的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其他需要数据随机分布的算法。

　　平均时间复杂度：尽管快速排序的最坏时间为 O(n^2 ), 但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，快速排序亦因此而得名。它的平均时间复杂度为 O(n×lgn)。

　　空间复杂度：快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 O(lgn), 故递归后所需栈空间为 O(lgn) 。最坏情况下，递归树的高度为 O(n), 所需的栈空间为 O(n) 。

　　稳定性：快速排序是非稳定的。