| 词条 | 快速排序 |
| 释义 | § 实现 快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为L[m..n]。 分解：序列L[m..n]被划分成两个可能为空的子序列L[m..pivot-1]和L[pivot+1..n]，使L[m..pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1..n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。 解决：通过递归调用快速排序，对子序列L[m..pivot-1]和L[pivot 1..r]排序。 合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m..n]已排好序。 § 性质 内部排序 快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。 比较排序 快速排序确定元素位置的方法基于元素之间关键字大小的比较。 所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》第8章。 快速排序在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。 不稳定性 快速排序是一种不稳定的排序方法。简单地说，元素a1,a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1,a2在排序后维持原来的位置先后关系。 原地排序 在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。 这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。 § 时空复杂度 快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。 而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。 快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。 但需要注意递归栈上需要花费最少logn最多n的空间。 § 随机化算法 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。” 随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。 § 减少递归栈使用的优化 快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。 一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。 一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。 阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。 另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。 § C例程 以下是C语言权威《TheCProgrammingLanguage》中的例程，在这个例程中，对于数组v的left到right号元素以递增顺序排序。 //Qsort.cbyTydus. #include<stdio.h> intarr[] = {14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7}; /*swap函数：交换v与v[j]的值*/ inlinevoidswap(intv[],inti,intj) { int temp = 0; temp = v; v = v[j]; v[j] = temp; } voidqsort(intv[],intleft,intright) { inti = 0 int last = 0; voidswap(intv[],inti,intj); if(left >= right)/*若数组包含的元素个数少于两个*/ return;/*则不执行任何操作*/ swap(v,left,(left right) / 2);/*将划分子集的元素*/ last = left;/*移动到v[0]*/ for(i = left 1; i <= right; i )/*划分子集*/ if(vswap(v, last,i); swap(v,left,last);/*恢复划分的元素*/ qsort(v,left,last - 1); qsort(v,last 1,right); } intmain(void) { qsort(arr,0,19); inti = 0; for(i = 0; i <= 19; printf("%d",arr[i ])); scanf("\"); return 0; } § C 例程 以下是一个用C 编写的快速排序程序。虽然C标准库中提供了快速排序，但作为快速排序的介绍，原理程序的代码更加有助于对快速排序运行过程的分析。 在这个例程中，对于数组x的0~n-1号元素的排序，初始调用为：quicksort(x,0,n-1); intquicksort_partition(intL[],intLbb,intUbb) { //随机化 intiRndPivID; srand(unsigned(time(0))); iRndPivID=(rand()%(Ubb-Lbb 1)) Lbb; swap(L[iRndPivID],L[Ubb]); //快排 intiPivValue; inti; intiPivPos; iPivValue=L[Ubb]; iPivPos=Lbb-1; for(i=Lbb;i<=Ubb-1;i ) { if(L[i]<=iPivValue) { iPivPos ; swap(L[iPivPos],L[i]); } } iPivPos ; swap(L[iPivPos],L[Ubb]); returniPivPos; } voidquicksort(intL[],intLbb,intUbb) { intiPiv; if(Lbb{ iPiv=quicksort_partition(L,Lbb,Ubb); quicksort(L,Lbb,iPiv-1); quicksort(L,iPiv 1,Ubb); } return; } § 使用C 标准库的快速排序函数 C 的标准库stdlib.h中提供了快速排序函数。 请在使用前加入对stdlib.h的引用：#include或#include qsort(void*base,size_tnum,size_twidth,int(*)compare(constvoid*elem1,constvoid*elem2)) 参数表 *base:待排序的元素（数组，下标0起）。 num:元素的数量。 width:每个元素的内存空间大小（以字节为单位）。可用sizeof()测得。 int(*)compare:指向一个比较函数。*elem1*elem2:指向待比较的数据。 比较函数的返回值 返回值是int类型，确定elem1与elem2的相对位置。 elem1在elem2右侧返回正数，elem1在elem2左侧返回负数。 控制返回值可以确定升序/降序。 一个升序排序的例程： intCompare(constvoid*elem1,constvoid*elem2) { return*((int*)(elem1))-*((int*)(elem2)); } intmain() { inta[100]; qsort(a,100,sizeof(int),Compare); return0; } § 算法基本思想 快速排序的基本思想是基于分治策略的。对于输入的子序列L【p..r】，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理： 分解(Divide)：将待排序列L【p..r】划分为两个非空子序列L【p..q】和L【q 1..r】，使L【p..q】中任一元素的值不大于L【q 1..r】中任一元素的值。具体可通过这样的途径实现：在序列L【p..r】中选择数据元素L【q】，经比较和移动后，L【q】将处于L【p..r】中间的适当位置，使得数据元素L【q】的值小于L【q 1..r】中任一元素的值。 递归求解(Conquer)：通过递归调用快速排序算法，分别对L【p..q】和L【q 1..r】进行排序。 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L【p..q】和L【q 1..r】都排好序后不需要执行任何计算L【p..r】就已排好序，即自然合并。 这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。 § 区别 快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为"分区交换排序"。 在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成"{左子序列}K{右子序列}"。再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。 分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：例如，可取左边第1个元素为分界点、取中点A【（left right）/2】为分界点、或选取最大和最小值的平均值为分界点等。 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。