分而治之算法描述

MergePass(b, a, s, n); // 从b 归并到a

s += s;

}

}

为了完成排序代码，首先需要完成函数M e rg e P a s s。函数M e rg e P a s s（见程序1 4 - 4）仅用来确定欲归并子序列的左端和右端，实际的归并工作由函数M e rg e (见程序1 4 - 5 )来完成。函数M e rg e要求针对类型T定义一个操作符< =。如果需要排序的数据类型是用户自定义类型，则必须重载操作符< =。这种设计方法允许我们按元素的任一个域进行排序。重载操作符< =的目的是用来比较需要排序的域。

程序14-4 MergePass函数

template<class T>

void MergePass(T x[], T y[], int s, int n)

{// 归并大小为s的相邻段

int i = 0;

while (i <= n - 2 * s) {

// 归并两个大小为s的相邻段

Merge(x, y, i, i+s-1, i+2*s-1);

i = i + 2 * s;

}

// 剩下不足2个元素

if (i + s < n) Merge(x, y, i, i+s-1, n-1);

else for (int j = i; j <= n-1; j++)

// 把最后一段复制到y

y[j] = x[j];

}

程序14-5 Merge函数

template<class T>

void Merge(T c[], T d[], int l, int m, int r)

{// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .

int i = l, // 第一段的游标

j = m+1, // 第二段的游标

k = l; // 结果的游标

/ /只要在段中存在i和j，则不断进行归并

while ((i <= m) && (j <= r))

if (c[i] <= c[j]) d[k++] = c[i++];

else d[k++] = c[j++];

// 考虑余下的部分

if (i > m) for (int q = j; q <= r; q++)

d[k++] = c[q];

else for (int q = i; q <= m; q++)

d[k++] = c[q];

}

自然归并排序（natural merge sort）是基本归并排序（见程序1 4 - 3）的一种变化。它首先对输入序列中已经存在的有序子序列进行归并。例如，元素序列[ 4，8，3，7，1，5，6，2 ]中包含有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，这些子序列是按从左至右的顺序对元素表进行扫描而产生的，若位置i 的元素比位置i+ 1的元素大，则从位置i 进行分割。对于上面这个元素序列，可找到四个子序列，子序列1和子序列2归并可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4归并可得[ 1 , 2 , 5 , 6 ]，最后，归并这两个子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，对于上述元素序列，仅仅使用了两趟归并，而程序1 4 - 3从大小为1的子序列开始，需使用三趟归并。作为一个极端的例子，假设输入的元素序列已经排好序并有n个元素，自然归并排序法将准确地识别该序列不必进行归并排序，但程序1 4 - 3仍需要进行[ l o g2 n] 趟归并。因此自然归并排序将在(n) 的时间内完成排序。而程序1 4 - 3将花费(n l o gn) 的时间。

 

2.2.3 快速排序

分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。

 

/ /使用快速排序方法对a[ 0 :n- 1 ]排序

从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点

把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点

递归地使用快速排序方法对left 进行排序

递归地使用快速排序方法对right 进行排序

所得结果为l e f t + m i d d l e + r i g h t

图14-9 快速排序的伪代码

 

考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。

把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。

程序14-6 快速排序

template<class T>

void QuickSort(T*a, int n)

{// 对a[0:n-1] 进行快速排序

{// 要求a[n] 必需有最大关键值

quickSort(a, 0, n-1);

template<class T>

void quickSort(T a[], int l, int r)

{// 排序a [ l : r ]， a[r+1] 有大值

if (l >= r) return;

int i = l, // 从左至右的游标

j = r + 1; // 从右到左的游标

T pivot = a[l];

// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换

while (true) {

do {// 在左侧寻找>= pivot 的元素

i = i + 1;

} while (a[i] < pivot);

do {// 在右侧寻找<= pivot 的元素

j = j - 1;

} while (a[j] > pivot);

if (i >= j) break; // 未发现交换对象

Swap(a[i], a[j]);

}

// 设置p i v o t

a[l] = a[j];

a[j] = pivot;

quickSort(a, l, j-1); // 对左段排序

quickSort(a, j+1, r); // 对右段排序

}

若把程序1 4 - 6中d o - w h i l e条件内的<号和>号分别修改为< =和> =，程序1 4 - 6仍然正确。实验结果表明使用程序1 4 - 6的快速排序代码可以得到比较好的平均性能。为了消除程序中的递归，必须引入堆栈。不过，消除最后一个递归调用不须使用堆栈。消除递归调用的工作留作练习（练习1 3）。程序1 4 - 6所需要的递归栈空间为O (n)。若使用堆栈来模拟递归，则可以把这个空间减少为O ( l o gn)。在模拟过程中，首先对left 和right 中较小者进行排序，把较大者的边界放入堆栈中。在最坏情况下l e f t总是为空，快速排序所需的计算时间为(n2 )。在最好情况下， l e f t和r i g h t中的元素数目大致相同，快速排序的复杂性为(nl o gn)。令人吃惊的是，快速排序的平均复杂性也是(nl o gn)。

定理2-1 快速排序的平均复杂性为(nl o gn)。

证明用t (n) 代表对含有n 个元素的数组进行排序的平均时间。当n≤1时，t (n)≤d，d为某一常数。当n <1时，用s 表示左段所含元素的个数。由于在中段中有一个支点元素，因此右段中元素的个数为n-s- 1。所以左段和右段的平均排序时间分别为t (s), t (n-s- 1 )。分割数组中元素所需要的时间用cn 表示，其中c 是一个常数。因为s 有同等机会取0 ~n- 1中的任何一个值.

如对（2 - 8）式中的n 使用归纳法，可得到t (n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8为自然对数的基底。在归纳开始时首先验证n= 2时公式的正确性。根据公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在归纳假设部分，假定t(n)≤kn l o ge n（当2≤n＜m 时，m 是任意一个比2大的整数＝.

图1 4 - 1 0对本书中所讨论的算法在平均条件下和最坏条件下的复杂性进行了比较。

 

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

冒泡排序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<nBreak) {InsertionSort(a,l,r); return;}

这里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）。

2.2.4 选择

对于给定的n 个元素的数组a [ 0 : n - 1 ]，要求从中找出第k小的元素。当a [ 0 : n - 1 ]被排序时，该元素就是a [ k - 1 ]。假设n = 8，每个元素有两个域k e y和I D，其中k e y是一个整数，I D是一个字符。假设这8个元素为[ ( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序后得到数组[ ( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h) ]。如果k = 1，返回I D为g 的元素；如果k = 8，返回I D为h 的元素；如果k = 6，返回是I D为f 的元素；如果k = 2，返回I D为d 的元素。实际上，对最后一种情况，所得到的结果可能不唯一，因为排序过程中既可能将I D为d 的元素排在a [ 1 ]，也可能将I D为b 的元素排在a [ 1 ]，原因是它们具有相同大小的k e y，因而两个元素中的任何一个都有可能被返回。但是无论如何，如果一个元素在k = 2时被返回，另一个就必须在k = 3时被返回。

选择问题的一个应用就是寻找中值元素，此时k = [n / 2 ]。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量。其他k值也是有用的。例如，通过寻找第n / 4 , n / 2和3 n / 4这三个元素,可将人口划分为4份。

选择问题可在O ( n l o g n )时间内解决，方法是首先对这n个元素进行排序（如使用堆排序式或归并排序），然后取出a [ k - 1 ]中的元素。若使用快速排序（如图1 4 - 11所示），可以获得更好的平均性能，尽管该算法有一个比较差的渐近复杂性O( n2 )。

可以通过修写程序1 4 - 6来解决选择问题。如果在执行两个w h i l e循环后支点元素a [ l ]被交换到a [ j ] ,那么a [ l ]是a [ l : j ]中的第j - l + 1个元素。如果要寻找的第k 个元素在a [ l : r ]中，并且j - l + 1等于k，则答案就是a [ l ]；如果j - l + 1 < k，那么寻找的元素是r i g h t中的第k - j + l - 1个元素，否则要寻找的元素是left 中的第k个元素。因此，只需进行0次或1次递归调用。新代码见程序1 4 - 7。S e l e c t中的递归调用可用f o r或w h i l e循环来替代（练习2 5）。

程序14-7 寻找第k 个元素

template<class T>