第9章 排序 9.1 排序的基本概念 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序 9.6 基数排序.

Presentation on theme: "第9章 排序 9.1 排序的基本概念 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序 9.6 基数排序."— Presentation transcript:

1 第9章 排序 9.1 排序的基本概念 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序 9.6 基数排序

2 9.1 排序的基本概念   排序（Sorting）是把一个无序的数据元素集合整理成按关键码递增（或递减）排列的有规律有序集合的过程。关键码是所定义的数据元素类型中的一个域。本节我们首先介绍讨论排序时经常用到的几个术语，然后给出比较排序算法好坏的几个基本标准。

3 1. 数据元素集合 一个数据元素集合可能是无限的，但对于我们这里讨论的要排序的数据元素集合一定要是有限的。数据元素集合用数据结构的术语也称作表。在第3章和第4章中指出，表既可以用顺序存储结构的数组存储，也可以用链式存储结构的链表存储。由于数组可随机存取，而链表存取操作的时间复杂度很难令人满意，所以本章讨论的排序算法的数据元素集合大部分都是使用数组存储的。

4 图9―1是一个数组存储的n个学生的成绩表。图9―1学生成绩表中的一行在非面向对象的软件分析和设计中称作一个记录，在面向对象的软件分析和设计中称作一个对象。我们用R表示对象，用R［0］,R［1］,R［2］,…,R［n-1］分别表示n个对象。

5 图9―1 一个顺序表结构的学生成绩表

6 2. 关键码 要排序的对象集合可能有多个域，关键码是当前排序时进行比较以确定各个对象位置的域。例如，对图9―1所示的学生成绩表，如果要求按学号排序，则学号域就是当前排序的关键码；如果要求按数学成绩排序，则数学域就是当前排序的关键码。关键码也可称作关键字，我们用K表示关键码。

7 在对象集合中，不同的对象其关键码值一定不相同的关键码称作主关键码（简称主码）；不同的对象其关键码值有可能相同的关键码称作次关键码（简称次码）。例如，图9-1的学生成绩表中的学号域就是主关键码，其他的域均是次关键码。

8 3. 排序算法的稳定性 任何排序算法当使用主关键码排序时，其排序结果一定是相同的。当排序算法使用次关键码排序时，其排序结果有可能相同，有可能不同。对于有n个对象集合中的次关键码K［i］(K［i］表示第i个对象的关键码)(i=0,1,2,…,n-1)，若K［i］等于K［j］(j=0,1,2,…,n-1,j≠i),且在排序之前对象R［i］排在对象R［j］之前，如果在排序之后对象R［i］仍在对象R［j］前边的排序算法称作稳定的排序算法，否则，称作不稳定的排序算法。

9 4. 排序算法的时间复杂度 和所有算法一样，时间复杂度也是衡量排序算法好坏的一个重要标准。排序算法的时间复杂度主要表现在算法中对象关键码的比较和对象的移动上。对于有n个对象集合的排序问题，因为从该集合中找出一个最大（或最小）对象一定要遍历该集合，其时间复杂度为O(n)，而进一步把n个对象均排列整齐的最理想情况可对应成完全二叉树结构，其时间复杂度为O(nlbn)，因此排序算法最好的时间复杂度是O(nlbn)。

10 5. 排序算法的空间复杂度 和所有算法一样，空间复杂度也是衡量排序算法好坏的一个重要标准。排序算法的空间复杂度也就是算法中使用的辅助存储单元的多少。当排序算法中使用的辅助存储单元与排序对象的个数n无关时，其空间复杂度为O(1)，因此排序算法最好的空间复杂度是O(1)。空间复杂度为O(1)的排序算法也称作原地排序算法。原地排序算法就是在原来存放对象集合的数组空间中重新按关键码大小排放对象集合。

11 6.内部排序和外部排序 排序分内部排序和外部排序。内部排序是把待排数据元素（或称对象）全部调入内存单元中进行的排序。外部排序时通常数据元素存放在外存介质（如磁盘、磁带等）上，这些数据元素的数量非常大，内存空间根本无法一次导入如此庞大的数据集合，需要分批导入，分批导入的数据排好序后再分批导出，分批导出的数据元素按关键码排序存放在外存介质上。

12 外部排序算法的原理和内部排序算法的原理很多都类同，但具体实现的函数差别很大。此外，由于访问外存的时间远远大于访问内存的时间，所以外部排序算法的时间复杂度主要由算法对外存介质的访问次数决定。限于篇幅，本书只讨论内部排序，不讨论外部排序，有兴趣的读者可参考相关文献。

13 在后面各节讨论的各种排序算法中，排序对象的数据类型是一个抽象类型。在各种具体的排序问题中，不同对象的数据域差别很大，而排序算法只与对象的关键码有关，因此不失一般性，我们定义排序算法中对象的抽象类型只包含关键码。其数据类型仍为抽象类型Keytype。为简化问题，本章给出的所有例子都假设Keytype为int类型，因此我们定义排序算法中对象的抽象类型为如下形式的结构体：

14 typedefintKeytype;structDatatype
{ Keytypekey; //构造函数 Datatype(){} Datatype(Keytypeitem):key(item){} //逻辑比较运算符 intoperator<=(constDatatype&item) {returnkey<=item.key;}

15 intoperator<(constDatatype&item)
{returnkey<item.key;} intoperator==(constDatatype&item) {returnkey==item.key;} intoperator>=(constDatatype&item) {returnkey>=item.key;} intoperator>(constDatatype&item) {returnkey>item.key;} intoperator!=(constDatatype&item) {returnkey!=item.key;} };

16 后边堆排序算法中的最小堆类将用到上述重载的逻辑比较操作符。其他排序算法中为简化算法描述，我们在算法中直接使用了对象的关键码比较，而没有用对象的比较。如直接插入排序算法中的比较语句：
temp.key<a［j］.key 上述抽象类型定义存放在文件Datatype.h中。

17 9.2 插入排序 9.2.1 直接插入排序 直接插入排序的基本思想是：顺序地把待排序的对象按其关键码值的大小插入到已排序对象集合的适当位置。
9.2 插入排序   9.2.1 直接插入排序 直接插入排序的基本思想是：顺序地把待排序的对象按其关键码值的大小插入到已排序对象集合的适当位置。 假设待排序的对象为R［0］,R［1］，R［2］，…,R［n-1］,开始排序时对象集合R［0］因只有一个对象,所以已排好序。第一次循环准备把对象,R［1］插入到已排好序的对象集合R［0］中，这只需比较K［0］和K［1］，若K［0］≤K［1］则已排好序，

18 否则将R［1］插入到R［0］之前，这样，对象集合R［0］,　R［1］已排好序。第二次循环准备把对象R［2］插入到已排好序的对象集合R［0］,　R［1］中，这需要先比较K［2］和K［1］以确定是否需要把R［2］插入到R［1］之前，然后比较K［2］和K［0］以确定是否需要把R［2］插入到R［0］之前；这样的循环过程一直进行到R［n-１］插入完为止。这时对象集合R［0］,R［1］,R［2］，…,R［n-1］就全部排好了序。直接插入排序算法的C[HT5”SS]++函数实现如下：

19 voidInsertSort(Datatypea［　］,intn)
//用直接插入法对a［0］--a［n-1］排序 {inti,j; Datatypetemp; for(i=0;i<n-1;i++) { temp=a［i+1］; j=i; while(j>-1&&temp.key<a［j］.key)

20 a［j+1］=a［j］; j--; } a［j+1］=temp;

21 图9―2是上述直接插入排序算法排序过程的一个示例。图中标有下划横线的对象为本次排序过程后移了一个位置的对象，标有符号□的对象为存放在临时变量temp中的对象。由于临时变量temp中保存了本次要插入对象的副本，所以原来存放该对象的内存单元可被破坏。

22 图9―2 直接插入排序过程

23 直接插入排序算法的时间复杂度分析可分最好和最坏两种情况考虑：
（1）最好情况是原始对象集合已全部排好序。这种情况下算法中的while循环的循环次数均为0。这样在每次排序过程中关键码的比较次数为1，对象的移动次数为2，因此整个排序过程中关键码的比较次数为n-1,对象的移动次数为2(n-1)，因此最好情况的时间复杂度为O(n)；

24 （2）最坏情况是原始对象集合全部逆序排列。这种情况下第i次排序时算法中的while循环的循环次数均为i。这样在每次排序过程中关键码的比较次数和对象的移动次数可计算如下：
比较次数= 移动次数= 因此最坏情况的时间复杂度为O(n2)。

25 如果原始对象集合中各对象的排列是随机的，则关键码的期望比较次数和对象的期望移动次数约为n2/4。因此，直接插入排序算法的期望时间复杂度为O(n2)。
可以证明：原始对象集合越接近有序，直接插入排序算法的时间效率越高，其时间效率在O(n)到O(n2)之间。这个结论是9.2.3节讨论的希尔排序能够成立的基础。 直接插入排序算法的空间复杂度为O(1)。显然，直接插入排序算法是一种稳定的排序算法。

26 测试图9―2例子的测试程序如下： ＃include<iostream.h>＃include"Datatype.h" voidmain(void) { Datatypetest［6］={64,5,7,89,6,24}; intn=6; InsertSort(test,n); for(inti=0;i<n;i++) cout<<test［i］.key<<""; } 测试程序的运行结果为：

27 9.2.2 链表插入排序 链表插入排序的最终排序结果将把对象集合按关键码大小依次链接地存储在一个链表中。这时链表中每个结点的结构除数据域外再要增加一个指向结点类型的指针域。 链表插入排序的思想是：初始时链表为空，第一个对象R［0］直接插入到链表中。第二个对象R［1］插入到链表中的位置由K［1］和K［0］比较确定：若K［1］<K［0］,则把R［1］插在R［0］前；否则把R［1］插在R［0］后。第三个对象R［2］插入到链表中的位置由K［2］和K［0］、K［1］的比较确定。若K［2］＜K［0］，则把R［2］插在R［0］前。

28 若K［2］＞K［0］，应比较K［2］、K［1］；若K［2］＜K［1］则把R［2］插在R［0］后、R［1］前，若K［2］＞K［1］则把R［2］插在R［1］后。这样的插入过程进行到R［n-１］插入完后，则原始对象集合按关键码大小依次链接在一个链表中。 链表中结点的数据类型定义为如下形式的结构体：   struct Node { Datatype data; //数据域 Node*next; //指针域 //构造函数

29 Node(Node*p=NULL):next(p){}
Node(Datatype item,Node*p=NULL):data(item),next(p){ } }; 结构体中第一个构造函数用于构造数据域值为空的头结点，第二个构造函数用于构造其他的存放数据元素的结点。

30 链表插入算法的C++函数实现如下： voidLinInsertSort(Datatypea［ ］,intn ,Node*list) //用链表插入法对a［0］--a［n-１］排序，排序结果存放在带头结点的单链表list中 { Node*curr,*pre,*q; for(inti=0;i<n;i++) curr=list->next; pre=list;

31 q=newNode(a［i］）; while(curr!=NULL&&curr->data.key<=a［i］.key) { pre=curr; curr=curr->next; } q->next=pre->next; pre->next=q;

32 注意，上述while循环的两个条件子语句：
curr!=NULL&&curr->data.key<=a［i］.key 的次序不能反；否则，在curr为NULL时，会由于curr→data.key不存在而出错。如果list为不带头结点的单链表，则插入时要考虑插在第一个结点前和插在第一个结点后的不同情况。8.3.2节中邻接表存储结构图类中插入边的成员函数InsertEdge(v1,v2,weight)就是链表插入排序算法中不带头结点的单链表的一个应用，该成员函数中所插入的边按弧尾顶点序号有序。

33 对于list为不带头结点的单链表的情况，读者可参照8. 3
对于list为不带头结点的单链表的情况，读者可参照8.3.2节中邻接表存储结构图类中插入边的成员函数InsertEdge(v1,v2,weight)作为练习自己完成。链表插入排序算法不需要移动数据对象，每插入一个对象时,最小关键码比较次数等于1，最大关键码比较次数等于链表中已排好序的对象个数，即 最小比较次数=n-1 最大比较次数= 所以，链表插入排序算法最坏情况的时间复杂度为O(n2)。  

34 链表插入排序算法另外需要n个结点空间存放排好序的数据对象，所以，链表插入排序算法的空间复杂度为O(n)。　链表插入排序算法中当后面插入对象的关键码和前面某次已插入对象的关键码相等时，让后面插入的对象存放在链表中前面与某次已插入的关键码相等对象的后面，具体实现体现在while循环的条件语句： curr->data.key<=a［i］.key 所以，链表插入排序算法是一种稳定的排序算法。

35 对象的后面，具体实现体现在while循环的条件语句：
curr->data.key<=a［i］.key 所以，链表插入排序算法是一种稳定的排序算法。链表插入算法LinInsertSort( )函数的测试程序如下：   ＃include<iostream.h> ＃include"Datatype.h"structNode { Datatypedata; //数据域 Node*next; //指针域

36 //构造函数 Node(Node*p=NULL):next(p){} Node(Datatypeitem,Node*p=NULL):data(item),next(p){ } }; voidmain(void) { Datatypetest［6］={64,5,7,89,6,24}; intn=6; Node*list=newNode; LinInsertSort(test,n,list); Node*p=list->next;

37 while(p!=NULL) { cout<<p->data.key<<""; p=p->next; } 测试程序的运行结果为：

38 9.2.3 希尔排序 希尔(Shell)排序又称作缩小增量排序，希尔排序算法的思想是：不断把待排序的对象分成若干个小组，对同一小组内的对象用直接插入法排序，当完成了所有对象都分在一个组内的排序后，排序过程结束。希尔排序是在分组概念上的插入排序，即在不断缩小组的个数时把原各小组的对象插入到新组中的合适位置上。

39 在9.2.1节讨论直接插入排序算法的时间复杂度时我们曾指出，原始对象集合越接近有序，直接插入排序算法的时间效率越高。这个结论是希尔排序算法能够成立的基础。希尔排序算法把待排序对象分成若干小组，在小组内用直接插入排序算法排序，当把小的小组合并为大一些的小组时，其中的对象集合将会接近有序，从而使直接插入排序算法的时间效率很高。 希尔排序算法的C++函数实现如下：

40 voidShellSort(Datatypea［ ］,intn,intd［ ］,intnumOfD)
//用希尔排序法对记录a［0］--a［n-1］排序，d［0］--d［numOfD-1］为增量值 { inti,j,k,m,span; Datatypetemp; for(m=0;m<numOfD;m++) //共numOfD次循环 span=d［m］;//取本次的增量值 for(k=0;k<span;k++) //共span个小组

41 //每个小组内按直接插入算法排序，区别只是每次不是增
1而是增span for(i=k;i<n-span;i=i+span) { temp=a［i+span］; j=i; while(j>-1&&temp.key<=a［j］.key) a［j+span］=a［j］; j=j-span; }

42 a［j+span］=temp; } 图9―3是上述希尔排序算法排序过程的一个示例。  

43 图9―3 希尔排序算法的排序过程

44 在图9―3所示的例子中，增量分别取6,3,1。第一重循环d［0］=6时，共分了6个小组，每个小组内按直接插入排序算法排序，这里的直接插入排序算法和9.2.1节讨论的直接插入排序算法的区别只是每次不是增1，而是增span。第三重循环d［2］=1的循环过程完成后，排序过程就结束了。

45 比较希尔排序算法和直接插入排序算法可见，直接插入排序算法是两重循环，希尔排序算法是四重循环，但分析希尔排序算法中四重循环的循环数值可以发现，四重循环每重的循环数值都很小，并且当增量递减、小组变大时，小组内的对象数值已基本有序，而我们知道，越接近有序的直接插入，排序算法的时间效率越高。因此，希尔排序算法的时间复杂度较直接插入排序算法的时间复杂度改善很多。

46 希尔排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，希尔排序算法的时间复杂度约为O(n(lbn)2)。

47 9.3 选择排序   9.3.1 直接选择排序 直接选择排序是一种简单且直观的排序方法。直接选择排序的思想是：从待排序的对象集合中选取关键码最小的对象并将它与原始对象集合中的第一个对象交换位置；然后从不包括第一个位置上对象的对象集合中选取关键码最小的对象并将它与原始对象集合中的第二个对象交换位置；如此重复，直到对象集合中只剩一个对象为止。  

48 直接选择排序算法的C ++函数实现如下： voidSelectSort(Datatypea［ ］,intn) //用直接选择排序法对a［0］--a［n-1］排序 { inti,j,small; Datatypetemp; for(i=0;i<n-1;i++) //逐个选取第0个到第n-2个对象 small=i; //设第i个对象关键码最小 for(j=i+1;j<n;j++) //寻找关键码最小的对象

49 if(a［j］.key<a［small］.key)small=j;
//记住最小对象的下标 if(small!=i) //当最小对象的下标不为i时交换位置 { temp=a［i］; a［i］=a［small］; a［small］=temp;} }

50 图9―4是上述直接选择排序算法排序过程的一个示例。
在直接选择排序算法中，第1次排序要进行n-1次比较，第2次排序要进行n-2次比较，…，第n-1次排序要进行1次比较，所以总的比较次数为 比较次数=(n-1)+(n-2)+…+1=n(n-1)/2 在各次排序时，对象的移动次数最好为0次，最坏为3次，所以总的移动次数最好为0次，最坏为3(n-1)次。因此，直接选择排序算法的时间复杂度为O(n2)。

51 图9―4 直接选择排序算法的排序过程

52 9.3.2 堆排序 堆排序是利用堆数据结构进行的排序方法。在7.7节讨论了堆这种数据结构，从7.7节的讨论可知，堆是结点间数据元素的关键码具有层次次序关系的完全二叉树。堆排序算法的思想是：建立一个堆结构的数组对象，不断删除堆顶对象并依次存于数组后面空出的存储单元中，当n个对象的数组中第n-1个对象被这样操作后，数组中的对象即排好序。 利用7.7.2节设计的最小堆类进行堆排序算法的C ++函数实现如下：

53 ＃include"MinHeap.h" voidHeapSort(Datatypea［ ］,intn) { MinHeap<Datatype>H1(a,n); //堆化数组a Datatypetemp; for(inti=n-1;i>0;i--) temp=H1.Delete( ); //删除堆顶对象 a［i］=temp; //存于数组后面空出的存储单元中 }

54 由于使用最小堆类每次删除并存于数组后面空出存储单元中的是当前数组（或说当前堆）中的最小对象，所以利用最小堆类实现的是从大到小的逆序排序，要实现从小到大的正序排序可使用最大堆类实现。
图9―5是8个元素从大到小的逆序堆排序算法排序过程的一个示例。 在7.7.2节我们曾分析指出，堆化数组最坏情况的时间复杂度为O(nlbn)，在堆中删除一个元素最坏情况的时间复杂度为O(lbn)。因此，堆排序算法最坏情况的时间复杂度为O(nlbn)。

55 图9―5 堆排序算法的排序过程

56 图9―5 堆排序算法的排序过程

57 图9―5 堆排序算法的排序过程

58 9.4 交换排序   9.4.1 冒泡排序 冒泡排序法是一种简单常用的排序方法。冒泡排序法的思想是：对n个对象的对象集合，设第一个对象的下标为0，依次把对象下标i定为0,1,2,…,n-2，然后依次将待排序对象集合中下标为i对象的关键码和下标为i+1对象的关键码进行比较，若前者大于后者，则交换两者位置；否则，不交换。

59 当这样的过程完成后，n个对象的数组的最后一个单元中就存放了对象集合中关键码最大的对象。然后，不考虑这个已排好序的对象，重新进行这样的过程，当这样的过程完成后，n-1个对象的数组的最后一个单元中就存放了对象集合中关键码最大的对象。当这样的过程进行n-1次，对象集合的数组中就是排好序的对象集合。

60 voidBubbleSort(Datatypea［］,intn)
//用冒泡排序法对a［0］--a［n-1］排序 { inti,j,flag=1; Datatypetemp; for(i=1;i<n&&flag==1;i++) flag=0; for(j=0;j<n-i;j++) if(a［j］.key>a［j+1］.key)

61 flag=1; temp=a［j］; a［j］=a［j+1］; a［j+1］=temp; }

62 函数中的标记flag用于判断本次交换排序过程是否有交换动作，若本次交换排序过程没有交换动作，则说明对象集合已全部排好序，就可提前结束排序过程。
图9―6是冒泡排序算法排序过程的一个示例。

63 图9―6 冒泡排序算法的排序过程

64 冒泡排序算法的最好情况是对象集合已全部排好序，这时循环n-1次，每次循环都因没有交换动作而退出，因此冒泡排序算法最好情况的时间复杂度为O(n)；冒泡排序算法的最坏情况是对象集合全部逆序存放，这时循环n-1次，每次循环的比较次数和交换移动次数为： 比较次数= 移动次数=

65 9.4.2 快速排序 快速排序又称作分区交换排序。快速排序算法的基本思想是：从待排序的对象数组中任取一个对象（通常是取对象数组中的第一个对象）作基准，调整对象数组中各个对象在数组中的位置，使排在该对象前面对象的关键码均小于该对象的关键码，使排在该对象后面对象的关键码均大于等于该对象的关键码。这样的交换过程结束后，一方面将该对象放在了未来排好序的对象数组中该对象应在的位置上；

66 另一方面将对象数组中的对象以该对象为基准分成了两个子对象数组，位于该基准对象左边子对象数组中对象的关键码均小于该对象的关键码，位于该基准对象右边子对象数组中对象的关键码均大于等于该对象的关键码。对于这两个子对象数组中的对象分别再进行方法类同的快速排序，当各个子对象数组中的对象个数均为1时，排序过程结束。显然，快速排序算法过程是递归的过程。 快速排序算法的C++函数实现如下：

67 voidQuickSort(Datatypea［］,intlow,inthigh)
//用递归方法对对象a［low］--a［high］进行快速排序 { inti=low,j=high; Datatypetemp=a［low］; //取第一个对象为进行调整的标准对象 while(i<j) //在数组的右端扫描 while(i<j&&temp.key<=a［j］.key)j--;

68 if(i<j) { a［i］=a［j］; i++; } //在数组的左端扫描 while(i<j&&a［i］.key<temp.key)i++; a［j］=a［i］; j--;

69 } a［i］=temp; //对子对象数组进行递归快速排序if(low<i)QuickSort(a,low,i-1); if(i<high)QuickSort(a,j+1,high);

70 快速排序算法过程是递归的过程，我们首先看第一次快速排序算法的执行过程。把任取的一个对象放在未来排好序的对象数组中该对象应在位置上的实现方法很多，但上述函数中的实现方法是一个高效的实现方法。该实现方法把定位过程分成两个过程：在对象数组的右端扫描定位和在对象数组的左端扫描定位。

71 在对象数组的右端扫描定位时，从对象数组的当前右端（设下标变量为j）开始，把所取的标准对象的关键码和数组右端对象的关键码比较。若标准对象的关键码小于等于数组右端对象的关键码，则数组下标减1继续比较；否则，转到在对象数组的左端扫描定位部分去执行。 在对象数组的左端扫描定位时，从对象数组的当前左端（设下标变量为i）开始，把所取的标准对象的关键码和数组左端对象的关键码比较。若标准对象的关键码大于数组左端对象的关键码，则数组下标加1继续比较否则，转到在对象数组的右端扫描定位部分去执行。

72 上述在对象数组的右端扫描定位和在对象数组的左端扫描定位反复进行，直到左端下标变量i大于等于右端下标变量j时为止。这时处于基准对象左边对象的关键码均小于标准对象的关键码，处于基准对象右边对象的关键码均大于等于标准对象的关键码。我们称这样的一次过程为一次快速排序。图9―7是快速排序算法一次快速排序过程的一个示例。对由基准对象划分的对象数组中两个子对象数组再分别递归地调用执行相应区间上的快速排序算法，当左端下标变量i大于等于右端下标变量j时，整个排序过程结束。图9―8是快速排序算法各次排序过程的一个示例。图中标有下划横线的对象为本次快速排序选取的基准对象。

73 图9―7 快速排序算法一次快速排序过程

74 图9―8 快速排序算法各次快速排序过程

75 对由基准对象划分的对象数组中两个子对象数组再分别 递归地调用执行相应区间上的快速排序算法，当左端下标变量i大于等于右端下标变量j时，整个排序过程结束。图9―8是快速排序算法各次排序过程的一个示例。图中标有下划横线的对象为本次快速排序选取的基准对象。

76 9.5 归并排序 归并排序就是逐步将若干个有序子表按两两一组或两个以上一组合并为一个有序表的方法。常用的归并排序算法是二路归并排序算法。
9.5 归并排序 归并排序就是逐步将若干个有序子表按两两一组或两个以上一组合并为一个有序表的方法。常用的归并排序算法是二路归并排序算法。 二路归并排序算法的思想是：设对象集合有n个对象，初始时我们把它们看成是n个长度为1的有序子表，然后从第一个子表开始，把相邻的子表两两合并，得到n/2的整数上界个长度为2的新的有序子表（当n为奇数时，最后一个新的有序子表的长度为1）；

77 对这些新的有序子表再做两两归并；如此重复，直到得到一个长度为n的有序表为止。一次二路归并排序算法的C++函数实现如下：
voidMerge(Datatypea［］,intn,Datatypeswap［］,intk) //对有序表a［0］--a［n-1］进行一次二路归并排序，每个有序子表的长度为k //一次二路归并排序后新的有序子表存于swap中 { intm=0,u1,l2,i,j,u2;  intl1=0; //给出第一个有序子表下界

78 while(l1+k<=n-1) { l2=l1+k; //计算第二个有序子表下界 u1=l2-1; //计算第一个有序子表上界 //计算第二个有序子表上界 //若剩余的对象个数小于k，则把剩余的对象作为最后一个子表，即情况（1） u2=(l2+k-1<=n-1)?l2+k-1:n-1; //两个有序子表合并 for(i=l1,j=l2;i<=u1&&j<=u2;m++) if(a［i］.key<=a［j］.key)

79 swap［m］=a［i］; i++; } else { swap［m］=a［j］; j++;  //子表2已归并完，将子表1中剩余的对象顺序存放到数组swap中

80 while(i<=u1) { swap［m］=a［i］; m++; i++; } //子表1已归并完，将子表2中剩余的对象顺序存放到数组swap中 while(j<=u2) swap［m］=a［j］; j++;

81 } l1=u2+1;} //将原始数组中只够一组的对象顺序存放到数组swap中，即情况（2） for(i=l1;i<n;i++,m++)swap［m］=a［i］;

82 一次二路归并排序算法的目标是把若干个长度为k的相邻有序子表从前向后两两进行归并，得到个数减半的长度为2k的相邻有序子表。算法设计中要考虑的一个问题是：若对象的个数为2k的整数倍时，两两归并正好完成n个对象的一次二路归并；否则当归并到某个对象位置时，剩余的对象个数不足2k个，这时的处理方法是： （1）若剩余的对象个数大于k而小于2k时，把前k个对象作为一个子表，把其他剩余的对象作为最后一个子表，然后采用同样的一次二路归并排序算法排序。  

83 （2）若剩余的对象个数小于k时，不用进行两两归并排序，直接把它们依次放入临时数组swap即可。
二路归并排序算法的C++函数实现如下： void MergeSort(Datatypea［］,intn) //用二路归并排序法对对象数组a［0］--a［n-1］排序 { inti,k=1; //归并长度由1开始 Datatype*swap=newDatatype［n］; //动态数组申请   while(k<n)

84 Merge(a,n,swap,k); for(i=0;i<n;i++)a［i］=swap［i］; //将对象从数组swap放回a中 k=2*k; //归并长度加倍 } delete［］swap; //释放动态数组

85 图9―9 二路归并排序算法各次归并排序过程

86 对n个对象进行二路归并排序时，归并的次数为lbn的整数上界，在任何一次的一次二路归并排序时，对象关键码的比较次数都为n-1，所以，二路归并排序算法的时间复杂度为O(nlbn)。二路归并排序使用了n个临时空间作对象临时存放用，所以，二路归并排序算法的空间复杂度为O(n)。

87 由于二路归并排序算法是相邻有序子表两两归并，对于关键码相同的对象，则能够保证原来在前面的排序后仍在前面，因此，二路归并排序算法是一种稳定的排序算法。前面讨论过的几个时间复杂度为O(nlbn)的排序算法都是不稳定的排序算法，而二路归并排序算法不仅时间复杂度也是O(nlbn)，而且它还是一种稳定的排序算法。这一点是二路归并排序算法的最大特点。

88 9.6 基数排序 基数排序也称作桶排序，是一种当关键码为整数类型时非常高效的排序方法。基数排序算法的基本思想是：设待排序的对象集合中对象的关键码是m位d进制整数（不足m位的关键码在高位补0），设置d个桶，令其编号分别为0,1,2,…,d-1。

89 首先按关键码最低位值的大小依次把各对象放到相应的桶中，然后按照桶号从小到大和进入桶中对象的先后次序收集分配在各桶中的对象，这样就形成了对象集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；再对一次基数排序得到的对象集合按关键码次低位值的大依次把各对象放到相应的桶中，再按照桶号从小到大和进入桶中对象的先后次序收集分配在各桶中的对象；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的结果。图9-10是基数排序算法排序过程的一个示例。

90 图9―10 基数排序算法排序过程

91 链式队列结构的基数排序算法的C++函数实现如下：
＃include"LinQueue.h" voidRadixSort(Datatypea［］,intn,intm,intd) //对对象a［0］--a［n-1］进行关键码为m位d进制整型数值的基数排序 //桶采用链式队列结构 { inti,j,k,l,power=1; LinQueue<Datatype>*tub=newLinQueue<Datatype>［d］;  //进行m次排序

92 for(i=0;i<m;i++) { if(i==0)power=1; elsepower=power*d; //将对象按关键码第k位的大小放到相应的队列中 for(j=0;j<n;j++) k=a［j］.key/power-(a［j］.key/(power*d))*d; tub［k］.QInsert(a［j］); }

93 //顺序回收各队列中的对象 for(j=0,k=0;j<d;j++) while(!tub［j］.QueueEmpty()) a［k++］=tub［j］.QDelete(); } 一个测试程序如下： ＃include<iostream.h> ＃include"Datatype.h"  voidmain(void) {

94 Datatypetest［］={710,342,45,686,6,841,429,134,68,246}; intn=10,m=3,d=10; RadixSort(test,n,m,d); for(inti=0;i<n;i++) cout<<test［i］.key<<""; }

95 链式队列结构的基数排序算法中要进行m次循环，每次循环中先要把n个对象放到相应的链式队列中，然后要把各个链式队列中的对象回收回来，链式队列的插入成员函数和删除成员函数的时间复杂度均是O(1)，所以，链式队列结构基数排序算法的时间复杂度为O(2mn)或者说O(mn)。m通常都不会很大，且m和对象个数n无关，所以链式队列结构基数排序算法的时间效率相当高。

96 在链式队列结构的基数排序算法中，要使用n个结点临时存放数据，所以，链式队列结构基数排序算法的空间复杂度为O(n)；从基数排序算法的思想可以得出，基数排序算法是一种稳定的排序算法。