《数据结构与算法》（二十五）- 排序算法：快速排序

前言

部分内容摘自程杰的《大话数据结构》

1. 快速排序

  快速排序算法最早由图灵奖获得者 Tony Hoare 设计出来的，他在形式化方法理论以及 ALGOL60 编程语言的发明中都有卓越的贡献，是上世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中的一个小发明而已。
  更牛的是，我们现在要学习的这个快速排序算法，被列为 20 世纪十大算法之一。我们这些玩编程的人还有什么理由不去学习它呢？
  希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。

1.1 快速排序算法

  快速排序（Quick Sort）的基本思想是：通过一趟排序将待排 记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小， 则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
  从字面上感觉不出它的好处来。假设现在要对数组 {50,10,90,30,70,40,80.60,20} 进行排序。我们通过代码的讲解来学习快速排序的精妙。
  我们来看代码。

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
	QSort(L,1,L->length);
}

  又是一句代码，和归并排序一样， 由于需要递归调用，因此我们外封装了一个函数。现在我们来看QSort的实现。

/* 对顺序表工中的子序列L->r[low. .high]作快速排序 */
void QSort(SqList *L,int low, int high)
{
	int pivot;
	if(low<high)
	{
		pivot=Partition(L,1ow,high);	/* 将L->r[1ow..high]一分为二，算出枢轴值pivot */
		QSort(L,low,pivot-1);	/* 对低子表递归排序 */
		QSort(L,pivot+1,high);	/* 对高子表递归排序 */
	}
}

  从这里，你应该能理解前面代码 “Qsort(L,1,L->length);” 中 1 和L->length代码的意思了，它就是当前待排序的序列最小下标值low和最大下标值high。
  这一段代码的核心是 “pivot=Partition(L,low,high);” 在执行它之前，L.r的数组值为 {50,10,90,30,70,40,80,60,20}。Partition函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大，我们将这样的关键字称为枢轴（pivot）。
  在经过Partition(L,1,9)的执行之后，数组变成 {20,10,40,30,5070,80,60,90}，并返回值 5 给pivot，数字 5 表明 50 放置在数组下标为 5 的位置。此时，计算机把原来的数组变成了两个位于 50 左和右小数组 {20,10,40,30} 和 {70,80,60,90}，而后的递归调用 “QSort(L,1,5-1);” 和 “QSort(L,5+1,9);” 语句，其实就是在对 {20,10,40,30} 和 {70,80,60,90} 分别进行同样的Partition操作，直到顺序全部正确为止。
  到了这里，应该说理解起来还不算困难。下面我们就来看看快速排序最关键的Partition函数实现。

/* 交换顺序表工中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
	int pivotkey;
	pivotkey=L->r[low];	/* 用子表的第一个记录作枢轴记录 */
	while(low<high)		/* 从表的两端交替向中间扫描 */
	{
		while(low<high&&L->r[high]>=pivotkey)
			high--;
		swap(L,low,high);	/* 将比枢轴记录小的记录交换到低端 */
		while(low<high&&L->r[low]<=pivotkey)
			low++;
		swap(L,low,high);	/* 将比枢轴记最大的记录交换到高端 */
	}
	return low;	/* 返回枢轴所在位置 */
}

1. 程序开始执行，此时low=1，high=L.length=9。第 4 行，我们将L.r[low]=L.r[1]=50赋值给枢轴变量pivotkey，如下图所示。
   
2. 第 5~13 行为while循环，目前low=1<high=9，执行内部语句。
3. 第 7 行，L.r[high]=L.r[9]=20>pivotkey=50，因此不执行第 8 行。
4. 第 9 行，交换L.r[ow]与L.r[high]的值，使得L.r[1]=20，L.r[9]=50。为什么要交换，就是因为通过第 7 行的比较知道，L.r[high]是一个比pivotkey=50 （即L.r[low]）还要小的值，因此它应该交换到 50 的左侧，如下图所示。
   
5. 第 10 行，当L.r[low]=L.r[1]=20，pivotkey=50，L.r[low]<pivotkey，因此第 11 行，low++，此时low=2。继续循环，L.r[2]=10<50，low++，此时low=3。L.r[3]=90>50，退出循环。
6. 第 12 行，交换L.r[low]=L.r[3]与L.r[high]=L.r[9]的值， 使得L.r[(3]=50，
   L.r[9]=90。此时相当于将一个比 50 大的值 90 交换到了 50 的右边。注意此时low已经指向了 3，如下图所示。
   
7. 继续第 5 行，因为low=3<high=9，执行循环体。
8. 第 7 行，当L.r[high]=L.r[9]=90，pivotkey=50，L.r[high]>pivotkey，因此第 8 行，high--，此时high=8。 继续循环，L.r[8]=60>50，high--，此时high=7。L.r[7]=-80>50，high--，此时high=6。L.r[6]=40<50，退出循环。
9. 第 9 行，交换L.r[low]=L.r[3]=50与L.r[high]=L.r[6]=40的值，使得L.r[3]=40，L.r[6]=50，如下图所示。
   
10. 第 10 行，当L.r[low]=L.r[3]=40，pivotkey=50，L.r[low]<pivotkey，因此第 11 行，low++，此时low=4。 继续循环L.r[4]=30<50，low++，此时low=5。L.r[5]=70>50，退出循环。
11. 第 12 行，交换L.r[low]=L.r[5]=70与L.r[high]=L.r[6]=50的值，使得L.r[5]=50，L.r[6]=70，如下图所示。
    
12. 再次循环。因low=5<high=6，执行循环体后，low=high=5，退出循环，如下图所示。
    
13. 最后第 14 行，返回low的值 5。函数执行完成。接下来就是递归调用 “QSort(L,1,5-1);” 和 “QSort(L,5+1,9);” 语句，对 {20,10,40,30} 和 {70,80,60,90} 分别进行同样的Parttion操作，直到顺序全部正确为止。我们就不再演示了。

  通过这段代码的模拟，大家应该能够明白，Partition函数，其实就是将选取的pivotkey不断交换，将比它小的换到它的左边，比它大的换到它的右边，它也在交换中不断更改自己的位置，直到完全满足这个要求为止。

1.2 快速排序算法复杂度分析

  我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如下图所示，它是 {50,10,90,30,70,40,80,60,20} 在快速排序过程中的递归过程。由于我们的第一个关键字是 50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

  在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为 $\lfloor log_2n\rfloor+1$（ $\lfloor x\rfloor$ 表示不大于 $x$ 的最大整数），即仅需递归 $log_2n$ 次，需要时间为 $T(n)$ 的话，第一次Partiation应该是需要对整个数组扫描一遍， 做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要 $T(n/2)$ 的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。

T(n)≤2T(n/2)+n,T(1)=0
T(n)≤2(2T(n/4)+n/2)+n=4T(n/4)+2n
T(n)≤4(2T(n/8)+n/4)+2n-8T(n/8)+3n
..... 
T(n)≤nT(1)+(1og2n)×n=O(nlogn)

  也就是说，在最优的情况下，快速排序算法的时间复杂度为 $O(nlogn)$。
  在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为 $\displaystyle \sum^{n-1}_{i=1}(n-i)=n-1+n-2+···+1=\frac{n(n-1)}{2}$，最终其时间复杂度为 $O(n^2)$。
  平均的情况，设枢轴的关键字应该在第k的位置（1<k≤n），那么：

$$T(n)=\frac{1}{n}\displaystyle \sum^n_{k=1}(T(k-1)+T(n-k))+n=\frac{2}{n}\displaystyle \sum^n_{k=1}T(k)+n$$

  由数学归纳法可证明，其数量级为 $O(nlogn)$。
  就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为 $log_2n$，其空间复杂度也就为 $O(logn)$，最坏情况，需要进行n-1递归调用，其空间复杂度为 $O(n)$，平均情况，空间复杂度也为 $O(logn)$。
  可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

1.3 快速排序优化

  刚才讲的快速排序还是有不少可以改进的地方，我们来看一些优化的方案。

• 优化选取枢轴

  如果我们选取的pivotkey是处于整个序列的中间位置，那么我们可以将整个序列分成小数集合和大数集合了。但注意，我刚才说的是 “如果…是中间”，那么假如我们选取的pivotkey不是中间数又如何呢？比如我们前面讲冒泡和简单选择排序一直用到的数组 {9,1,5,8,3,7,4,6,2}，由代码第 4 行 “pivotkey=L->r[ow];” 知道，我们应该选取 9 作为第一个枢轴pivotkey。此时，经过一轮 “pivot=Partition(L,1,9);” 转换后，它只是更换了 9 与 2 的位置，并且返回 9 给pivot，整个系列并没有实质性的变化，如下图所示。

  就是说，代码第 4 行 “pivotkey=L->r[low];” 变成了一个潜在的性能瓶颈。排序速度的快慢取决于L.r[1]的关键字处在整个序列的位置，L.r[1]太小或者太大，都会影响性能（比如第一例子中的 50 就是一个中间数，而第二例子的 9 就是一个相对整个序列过大的数）。因为在现实中，待排序的系列极有可能是基本有序的，此时，总是固定选取第一个关键字（其实无论是固定选取哪一个位置的关键字）作为首个枢轴就变成了极为不合理的作法。
  改进办法，有人提出，应该随机获得一个low与high之间的数rnd，让它的关键字L.r[rnd]与L.r[low]交换， 此时就不容易出现这样的情况，这被称为随机选取枢轴法。应该说，这在某种程度上，解决了对于基本有序的序列快速排序时的性能瓶颈。不过，随机就有些撞大运的感觉，万一没撞成功，随机到了依然是很小或很大的关键字怎么办呢？
  再改进，于是就有了三数取中（median-of-three）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。
  我们来看看取左端、右端和中间三个数的实现代码，在Partition函数代码的第 3 行与第 4 行之间增加这样一段代码。

int pivotkey;

int m=low+(high-low)/2;	/* 计算数组中间的元素的下标 */
if (i->r[low]>L->r[high])
	swap(L,low,high);	/* 交换左端与右端数据，保证左端较小 */
if (L->r[m]>L->r[high])
	swap(L,high,m);		/* 交换中间与右端数据，保证中间较小 */
if (L->r[m]>L->r[low] )
	swap(L,m,low);		/* 交换中间与左端数据，保证左端较小 */
/* 此时L.r[low]已经为整个序列左中右三个关键宇的中间值。 */
pivotkey=L->r[low];	/* 用子表的第一个记录作枢轴记录古 */

  试想一下，我们对数组 {9,1,5,8,3,7,4,6,2}，取左 9、中 3、右 2来比较，使得L.r[low]=3，一定要比 9 和 2 来得更为合理。
  三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有个办法是所谓九数取中（median-of-nine），它先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然这就更加保证了取到的pivotkey是比较接近中间值的关键字。有兴趣的同学可以自已去实现一下代码，这里不再详述了。

• 优化不必要的交换

  观察前面快速排序的六张图，我们发现，50 这个关键字，其位置变化是 1→9→3→6→5，可其实它的最终目标就是 5，当中的交换其实是不需要的。因此我们对Partition函数的代码再进行优化。

/* 快速排序优化算法 */
int Partitionl(SqList *L,int low, int high) 
{
	int pivotkey;
	//这里省略三数取中代码
	pivotkey=L->r[low];	/* 用子表的第一个记录作枢轴记最 */。
	L->r[0]=pivotkey;	/* ★★★将枢轴关键宇备份到L->r[0] */
	while(low<high)		/* 从表的两端交替向中间扫描 */
	{
		while(low<high&&L->r[high]>=pivotkey)
			high--i
		L->r[low]=L->r[high];	/* ★★★采用替换而不是交换的方式进行操作 */
		while(low<high&&L->r[low]<-pivotkey)
			low++;
		L->r[high]=L->r[low];	/* ★★★采用替换而不是交换的方式进行操作 */
	}
	L->r[low]=L->x[0];	/* ★★★将枢轴数值替换回L.r[low] */
	return low;			/* 返回枢轴所在位置 */
}

  注意代码中加★★★部分的改变。我们事实将pivotkey备份到L.r[0]中， 然后在之前是swap时，只作替换的工作，最终当low与high会合，即找到了枢轴的位置时，再将L.r[0]的数值赋值回L.r[low]。因为这当中少了多次交换数据的操作，在性能上又得到了部分的提高。如下图所示。

• 优化小数组时的排序方案
    对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培养最优秀的数学博士，但让他去教小学生 “1+1=2” 的算术课程，那还真未必会比常年在小学里耕耘的数学老师教得好。换句话说，大材小用有时会变得反而不好用。刚才我谈到了对于非常大的数组的解决办法。那么相反的情况，如果数组非常小，其实快速排序反而不如直接插入排序来得更好（直接插入是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了一个大炮打蚊子的大问题。因此我们需要改进一下QSort函数。

#define MAX_LENGTH_INSERT_SORT 7	/* 数组长度阀值 */
/* 对顺序表工中的子序列L.r[low..high]作快速排序 */
void QSort(Sqlist SL,int low,int high)
{
	int pivot;
	if((high-low)>MAX_LENGTH_INSERT_SORT)
	{/* 当high-1ow大于常数时用快速排序 */
		pivot=Partition(L,low,high);	/* 将L.r[1ow..high]一分为二，并算出枢轴值pivot */
		QSort(L,low,p1vot-1);	/* 对低子表递归排序 */
		QSort(L,pivot+1,high);	/* 对高子表递归排序 */
	}
	else	/* 当high-low小于等于常数时用直接插入排序 */
		InsertSort(L);
}

  我们增加了一个判断，当high-low不大于某个常数时（有资料认为 7 比较合适，也有认为 50 更合理，实际应用可适当调整），就用直接插入排序，这样就能保证最大化地利用两种排序的优势来完成排序工作。

• 优化递归操作

  大家知道，递归对性能是有一定影响的，QSort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的 $log_2n$，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。
  于是我们对QSort实施尾递归优化。来看代码。

/* 对顺序表工中的子序列L.r[low..high]作快速排序 */
void QSort1(SqList *L,int low, int high)
{
	int pivot;
	if ((high-low) > MAX_LENGTH_INSERT_SORT)
	{
		while(low<high)		/* ★★★ */
		{
			pivot=Partitionl(L,low,high);	/* L.r[low. .high]一分为二,算出枢轴值pivot */ 
			QSort1(L,low,pivot-1);	/* 对低子表递归排序 */
			low=pivot+1;	/* ★★★尾递归 */
		}
	}
	else
		InsertSort(L);
}

  当我们将if改成while后（见加★★★代码部分），因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Parttion(L,low,high)，其效果等同于 “QSort(L,pivot+1,high) ;” 。 结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。
  在现实的应用中，比如C++、java、 PHP、C#、 VB、JavaScript 等都有对快速排序算法的实现，实现方式上略有不同，但基本上都是在我们讲解的快速排序法基础上的精神体现。

• 了不起的排序算法

  我们现在学过的排序算法，有按照实现方法分类命名的，如简单选择排序、直接插入排序、归并排序，有按照其排序的方式类比现实世界命名的，比如冒泡排序、堆排序，还有用人名命名的，比如希尔排序。但是刚才我们讲的排序，却用 “快速” 来命名，这也就意味着只要再有人找到更好的排序法，此 “快速” 就会名不符实，不过，至少今天，TonyHoare 发明的快速排序法经过多次的优化后，在整体性能上，依然是排序算法王者，我们应该要好好研究并掌握它。

2. 总结

  我们根据将排序记录是否全部被放置在内存中，将排序分为内排序与外排序两种，外排序需要在内外存之间多次交换数据才能进行。我们本章主要讲的是内排序的算法。
  根据排序过程中借助的主要操作，我们将内排序分为：插入排序、交换排序、选择排序和归并排序四类。之后介绍的 7 种排序法，就分别是各种分类的代表算法。

  事实上，目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们就来从多个角度来剖析一下提到的各种排序的长与短。
  我们将 7 种算法的各种指标进行对比，如下表所示。

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(nlogn)$~$O(n^2)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	稳定
快速排序	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(nlogn)$~$O(n)$	不稳定

  从平均情况来看，显然最后 3 种改进算法要胜过希尔排序，并远远胜过前 3 种简单算法。
  从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑 4 种复杂的改进算法。
  从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。
  从这三组时间复杂度的数据对比中，我们可以得出这样一个认识。 堆排序和归并排序就像两个参加奥数考试的优等生，心理素质强，发挥稳定。而快速排序像是很情绪化的天才，心情好时表现极佳，碰到较糟糕环境会变得差强人意。但是他们如果都来比赛计算个位数的加减法，它们反而算不过成绩极普通的冒泡和直接插入。
  从空间复杂度来说，归并排序强调要马跑得快，就得给马吃个饱。快速排序也有相应的空间要求，反而堆排序等却都是少量索取，大量付出，对空间要求是 $O(1)$。 如果执行算法的软件所处的环境非常在乎内存使用量的多少时，选择归并排序和快速排序就不是一个较好的决策了。
  从稳定性来看，归并排序独占鳌头，我们前面也说过，对于非常在乎排序稳定性的应用中，归并排序是个好算法。
  从待排序记录的个数上来说，待排序的个数n越小，采用简单排序方法越合适。反之，n越大，采用改进排序方法越合适。这也就是我们为什么对快速排序优化时，增加了一个阀值，低于阀值时换作直接插入排序的原因。
  从上表的数据中，似乎简单选择排序在 3 种简单排序中性能最差，其实也不完全是，比如，如果记录的关键字本身信息量比较大（例如，关键字都是数十位的数字），此时表明其占用存储空间很大，这样移动记录所花费的时间也就越多，我们给出 3 种简单排序算法的移动次数比较，如下表所示。

排序方法	平均情况	最好情况	最坏情况
冒泡排序	$O(n^2)$	0	$O(n^2)$
简单选择排序	$O(n)$	0	$O(n)$
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$

  你会发现，此时简单选择排序就变得非常有优势，原因也就在于，它是通过大量比较后选择明确记录进行移动，有的放矢。因此对于数据量不是很大而记录的关键字信息量较大的排序要求，简单排序算法是占优的。另外，记录的关键字信息量大小对那四个改进算法影响不大。
  总之，从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对它。