c语言算法 - 分而治之算法 - 快速排序

核心提示：方法最坏复杂性平均复杂性冒泡排序n2 n2计数排序n2 n2插入排序n2 n2选择排序n2 n2堆排序nl o gn nl o gn归并排序nl o gn nl o gn快速排序n2 nl o gn图14-10 各种排序算法的比较中值快速排序（median-of-three quick sort）是程序1 4 - 6的

方法最坏复杂性平均复杂性

冒泡排序n2 n2

计数排序n2 n2

插入排序n2 n2

选择排序n2 n2

堆排序nl o gn nl o gn

归并排序nl o gn nl o gn

快速排序n2 nl o gn

图14-10 各种排序算法的比较

中值快速排序（median-of-three quick sort）是程序1 4 - 6的一种变化，这种算法有更好的平均性能。注意到在程序1 4 - 6中总是选择a[ 1 ]做为支点，而在这种快速排序算法中，可以不必使用a[ 1 ]做为支点，而是取{a[1],a[(1+r)/2],a[r]}中大小居中的那个元素作为支点。例如，假如有三个元素，大小分别为5，9，7，那么取7为支点。为了实现中值快速排序算法，一种最简单的方式就是首先选出中值元素并与a[1]进行交换，然后利用程序1 4 - 6完成排序。如果a[ r ]是被选出的中值元素，那么将a[1] 与a[r]进行交换，然后将a[ 1 ]（即原来的a[ r ]）赋值给程序1 4 - 6中的变量p i v o t，之后继续执行程序1 4 - 6中的其余代码。

图2 - 11中分别给出了根据实验所得到的归并排序、堆排序、插入排序、快速排序的平均时间。对于每一个不同的n, 都随机产生了至少1 0 0组整数。随机整数的产生是通过反复调用s t d l i b . h库中的r a n d o m函数来实现的。如果对一组整数进行排序的时间少于1 0个时钟滴答，则继续对其他组整数进行排序，直到所用的时间不低于1 0个时钟滴答。在图2 - 11中的数据包含产生随机整数的时间。对于每一个n，在各种排序法中用于产生随机整数及其他开销的时间是相同的。因此，图2 - 11中的数据对于比较各种排序算法是很有用的。

对于足够大的n，快速排序算法要比其他算法效率更高。从图中可以看到快速排序曲线与插入排序曲线的交点横坐标比2 0略小，可通过实验来确定这个交点横坐标的精确值。可以分别用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9进行实验，以寻找精确的交点。令精确的交点横坐标为nBr e a k。当n≤nBreak 时，插入排序的平均性能最佳。当n＞nBreak 时，快速排序性能最佳。当n＞nBreak 时，把插入排序与快速排序组合为一个排序函数，可以提高快速排序的性能，实现方法是把程序1 4 - 6中的以下语句：

if(l >= r)r e t u r n ;

替换为

if(r-1

这里I n s e r t i o n S o r t( a , l , r )用来对a[ 1 : r ]进行插入排序。测量修改后的快速排序算法的性能留作练习（练习2 0）。用更小的值替换n B r e a k有可能使性能进一步提高（见练习2 0）。

大多数实验表明，当n＞c时（c为某一常数），在最坏情况下归并排序的性能也是最佳的。而当n≤c时，在最坏情况下插入排序的性能最佳。通过将插入排序与归并排序混合使用，可以提高归并排序的性能（练习2 1）。