快速排序 Thinking in QuickSort

快速排序

1.大致的介绍：

　　快速排序(QuickSort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。

　　快速排序被认为是当前最优秀的内部排序方法。

2.实现

　　快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为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]已排好序。

3.性质

　　内部排序

　　快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。

　　比较排序

　　快速排序确定元素位置的方法基于元素之间关键字大小的比较。

　　所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》（第一版）第8章（第二版在第七章QuickSort)。

　　在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。

　　不稳定性

　　快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。

　　原地排序

　　在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。

　　这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。

4.时空复杂度

　　快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。

　　而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。

　　快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。

　　但需要注意递归栈上需要花费最少logn 最多n的空间。

5.随机化算法

　　快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”

　　随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。

6.减少递归栈使用的优化

　　快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。

　　一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。

　　一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。

　　阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。

　　另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。

7.C语言代码实现如下，头文件中不要引用stdlib.h这个头文件，此中已经定义了qsort这个函数，编译会出错：

#include <stdio.h>

int partions(int l[],int low,int high)
{
int prvotkey=l[low];
l[0]=l[low];
while (low<high)
{
while (low<high&&l[high]>=prvotkey)
{
--high; //从右端开始，检索小于参照值得数据，若没有一次左移
}


l[low]=l[high]; //检测到后作交换


while (low<high&&l[low]<=prvotkey)
{
++low; //从左端低位开始，检索大于参照值得数据，若没有一次右移
}

l[high]=l[low];
}


l[low]=l[0];
return low;
}

void qsort(int l[],int low,int high)
{
int prvotloc;
if(low<high)
{
prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴
qsort(l,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1
qsort(l,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high
}
}

void quicksort(int l[],int n)
{
qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个
}

int main()
{
int a[11]= {0};
int d,b,c;

for(d=1;d<11;d++)
{
printf("Input : ");
scanf("%d",a+d);
}


for (b=1; b<11; b++)
{
printf("%3d",a[b]);
}

printf("\n");
quicksort(a,11);


for(c=1; c<11; c++)
{
printf("%3d",a[c]);
}
printf("\n");

return 0;

}

运行结果如下：