爱华网快速排序(QuickSort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法。
快速排序_快速排序 -实现
快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为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("n");
return 0;
}
快速排序_快速排序 -使用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】为分界点、或选取最大和最小值的平均值为分界点等。
快速排序_快速排序 -伪代码
非随机
QUICKSORT(A，p，r)
1ifp<r
2thenq←PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
为排序一个完整的数组A，最初的调用是QUICKSORT(A，1，length[A]）。
快速排序算法的关键是PARTITION过程，它对子数组A[p..r]进行就地重排：
PARTITION(A，p，r)
1x←A[r]
2i←p-1
3forj←ptor-1
4doifA[j]≤x
5theni←i+1
6exchangeA[i]←→A[j]
7exchangeA[i+1]←→A[r]
8returni+1[2]
随机
对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中，我们在真正进行划分之前实现交换：
（其中PARTITION过程同快速排序伪代码（非随机））
RANDOMIZED-PARTITION(A，p，r)
1i←RANDOM(p，r)
2exchangeA[r]←→A[i]
3returnPARTITION(A，p，r)
新的快速排序过程不再调用PARTITION，而是调用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1ifp<r
2thenq←RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r)[2]
性能分析
这里为方便起见，我们假设算法Quick_Sort的范围阈值为1（即一直将线性表分解到只剩一个元素），这对该算法复杂性的分析没有本质的影响。
我们先分析函数partition的性能，该函数对于确定的输入复杂性是确定的。观察该函数，我们发现，对于有n个元素的确定输入L[p..r]，该函数运行时间显然为θ（n）。
最坏情况
无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情况都是相同的。
我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候（设输入的表有n个元素）。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。
对于有n个元素的表L[p..r]，由于函数Partition的计算时间为θ（n），所以快速排序在序坏情况下的复杂性有递归式如下：
T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n)(1)
用迭代法可以解出上式的解为T(n)=θ（n2）。
这个最坏情况运行时间与插入排序是一样的。
下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。
设T(n）是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间，则
T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1(2)
我们假设对于任何k<n，总有T(k）≤ck，其中c为常数；显然当k=1时是成立的。
将归纳假设代入（2），得到：
T(n）≤max(cq2+c(n-q)2)+θ（n)=c*max(q2+(n-q)2)+θ（n)
因为在[1,n-1]上q2+(n-q)2关于q递减，所以当q=1时q2+(n-q)2有最大值n2-2(n-1）。于是有：
T(n）≤cn2-2c(n-1)+θ（n）≤cn2
只要c足够大，上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n）≤cn。
这样，排序算法的最坏情况运行时间为θ（n2），且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。
时间复杂度为o（n2）。
最好情况
如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。这时有：
T(n)=2T(n/2)+θ（n),T(1)=θ（1)(3)
解得：T(n)=θ（nlogn)
快速排序法最佳情况下执行过程的递归树如下图所示，图中lgn表示以10为底的对数，而本文中用logn表示以2为底的对数.
由于快速排序法也是基于比较的排序法，其运行时间为Ω（nlogn)，所以如果每次划分过程产生的区间大小都为n/2，则运行时间θ（nlogn）就是最好情况运行时间。
但是，是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍一看该划分很不对称。我们可以得到递归式：
T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1)(4)
请注意树的每一层都有代价n，直到在深度log10n=θ（logn）处达到边界条件，以后各层代价至多为n。递归于深度log10/9n=θ（logn）处结束。这样，快速排序的总时间代价为T(n)=θ（nlogn），从渐进意义上看就和划分是在中间进行的一样。事实上，即使是99:1的划分时间代价也为θ（nlogn）。其原因在于，任何一种按常数比例进行划分所产生的递归树的深度都为θ（nlogn），其中每一层的代价为O(n），因而不管常数比例是什么，总的运行时间都为θ（nlogn），只不过其中隐含的常数因子有所不同。（关于算法复杂性的渐进阶，请参阅算法的复杂性)
快速排序的平均运行时间为θ(nlogn)。
我们对平均情况下的性能作直觉上的分析。
要想对快速排序的平均情况有个较为清楚的概念，我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。
当我们对一个随机的输入数组应用快速排序时，要想在每一层上都有同样的划分是不太可能的。我们所能期望的是某些划分较对称，另一些则很不对称。事实上，我们可以证明，如果选择L[p..r]的第一个元素作为支点元素，Partition所产生的划分80%以上都比9:1更对称，而另20%则比9:1差，这里证明从略。
平均情况下，Partition产生的划分中既有“好的”，又有“差的”。这时，与Partition执行过程对应的递归树中，好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致，假设好、差划分交替出现在树的各层上，且好的划分是最佳情况划分，而差的划分是最坏情况下的划分。在根节点处，划分的代价为n，划分出来的两个子表的大小为n-1和1，即最坏情况。在根的下一层，大小为n-1的子表按最佳情况划分成大小各为（n-1)/2的两个子表。这儿我们假设含1个元素的子表的边界条件代价为1。
在一个差的划分后接一个好的划分后，产生出三个子表，大小各为1，（n-1)/2和（n-1)/2，代价共为2n-1=θ（n）。一层划分就产生出大小为（n-1)/2+1和（n-1)/2的两个子表，代价为n=θ（n）。这种划分差不多是完全对称的，比9:1的划分要好。从直觉上看，差的划分的代价θ（n）可被吸收到好的划分的代价θ（n）中去，结果是一个好的划分。这样，当好、差划分交替分布划分都是好的一样：仍是θ（nlogn），但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出。
在前文从直觉上探讨快速排序的平均性态过程中，我们已假定输入数据的所有排列都是等可能的。如果输入的分布满足这个假设时，快速排序是对足够大的输入的理想选择。但在实际应用中，这个假设就不会总是成立。
解决的方法是，利用随机化策略，能够克服分布的等可能性假设所带来的问题。
一种随机化策略是：与对输入的分布作“假设”不同的是对输入的分布作“规定”。具体地说，在排序输入的线性表前，对其元素加以随机排列，以强制的方法使每种排列满足等可能性。事实上，我们可以找到一个能在O(n）时间内对含n个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间，但它却使得运行时间能够独立于输入数据已排序的情况。
另一种随机化策略是：利用前文介绍的选择支点元素pivot的第四种方法，即随机地在L[p..r]中选择一个元素作为支点元素pivot。实际应用中通常采用这种方法。
快速排序的随机化版本有一个和其他随机化算法一样的有趣性质：没有一个特别的输入会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意给出一个坏的输入也没用，因为随机化排列会使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时，随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态，只有非常少的几个排列才会导致算法的近最坏情况性态。
一般来说，当一个算法可按多条路子做下去，但又很难决定哪一条保证是好的选择时，随机化策略是很有用的。如果大部分选择都是好的，则随机地选一个就行了。通常，一个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价，那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到，对快速排序来说，一组好坏相杂的划分仍能产生很好的运行时间[2]。因此我们可以认为该算法的随机化版本也能具有较好的性态。
