快速排序是大多数系统选择的排序算法。在基于UNIX和Linux的系统中,有内建的库函
数qsort(有些版本的Linux模作系统是使用堆排序来实现qsort的,在接下来的“堆排序”中将会讲到)。操作系统经常使用的是优化过的快速排序算法。在论述如何优化的资源中,两个经常被引用的是Sedgewick(1978)和Bentley与Mcllroy(1993)。
各种各样的优化:
1.利用存储子任务的栈来消除递归。
2.选择基于三中值分区的中枢值。
3.设定一个使用切分时数组长度的最小值,如果小于这个值,就使用插入排序(这个值根据实现和机器架构的不同而不同;例如,在Sun4架构上,这个最小值根据经验,一般设定为4)。
4.当处理子数组的时候,首先将大的子数组压入树中,这样来最小化树的总大小,确保小的问题首先被解决。
认识到这样一个问题是非常重要的,那就是这些优化都不能够使最坏情况下快速排序的
性能高于O(n²)。唯一能够确保最坏情况下O(
n
l
o
g
n
nlogn
nlogn)性能的是使用例如BFPRT的选择算法,虽然使用这个算法会使平均情况下的性能降低,。如果要求最坏情况下O(
n
l
o
g
n
nlogn
nlogn)的性能,那么考虑使用堆排序,这个算法将在接下来讲述。
选择中枢值
从一个子数组A[left.left+n)中选择一个中枢元素的操作必须是高效的,不应该需要检查子数组中的所有n个元素。有一些改进如下:
1.选择第一个或者最后一个:A[left]或者A[lefttn-1]。
在A[left,left+n-1]中选择一个随机元素。
选择k中值:在A[left,left+n-1]随机选择k个元素,然后选择这k个元素的中值。
通常我们都选择k=3,这个变种叫做三中值。Sedgewick描述了这个方法,并且认为这个
改进能够有5%的性能提升,不过他注意到数据的某些排列将会使得算法,包括这个改进
的性能在一般水准以下。一个五中值的中枢值选择也投入使用。这个改进进行更深入的计算来选择合适的中枢值,由于带来了过多开销,所以很少能够得到性能提升。这种改
进使得性能和中值排序的性能很接近(事实上,中值排序也会接受这种选择n中值的极端变化)。
处理切分
在前面的切分函数中,小于或者等于中枢元素的值的元素都被插入到子数组的前端。如果数组中有很多和选择的中枢元素重复的元素,这个方法也许会使得子数组的大小不平衡。一种减少失衡问题的解决方法是将等于中枢元素值的元素轮流地插入到第一个和第二个子数组中。
处理子数组
快速排序通常在切分出来的两个子数组上分别进行递归调用快速排序。当处理一个子数组时,另一个的活动记录将会被压入执行找中。如果大的子数组首先被处理,那么此时
树中可能存储了线性数目的活动记录(虽然现代编译器也许会观察到并且消除这个开
销)。为了最小化树的可能深度,那么首先处理小的子数组。
如果系统栈的深度是可预见的,那么快速排序也许不适合你的应用程序。一种打破这个
值局的方法是使用一个栈的数据结构来存储将要解决的子问题,而不是依赖于递归。
为小数组使用简单的插入排序在小数组上,插入排序比快速排序要快得多,当处理大数组时,快速排序最终还是将大数组切分成无数的待排序的小数组。为了改善快速排序的递归性能,一个广泛使用的技术是在排序大子数组时调用快速排序,在排序小子数组时使用插入排序Sedgewick(1978)建议在快速排序中结合三中值和在排序小数组时使用插入排序这两种手段,这样能够相比纯快速排序提高20%~25%的性能。
内观排序
是否切换到对小数组的插入排序取决于数组的大小。Musser(1997)介绍了一个快速排序的变种,叫做内观排序(IntroSort),这个算法监视快速排序的递归深度,以确保高效地处理。如果快速排序的递归深度超过log(n)级,那么内观排序切换到堆排序。C++STL的SGI实现使用了内观排序作为其默认的排序算(http://www.sgi.com/tech/stl/sort.html)。