1、第10章 排序 陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓第1页，共91页。本章目录10.1 概述概述10.2 插入排序插入排序 10.2.1 直接插入排序直接插入排序 10.2.2 折半插入排序折半插入排序 *10.2.3 二路插入排序二路插入排序 *10.2.4 表插入排序表插入排序 10.2.5 希尔排序希尔排序10.3 交换排序交换排序 10.3.1 起泡排序起泡排序 10.3.2 快速排序快速排序10.4 选择排序选择排序 10.4.1 直接选择排序直接选择排序 10.4.2 树形选择排序树形选择排序10.4.3 堆排序堆排序10.5 归并排序归并排序10.6 分配排序分配排序10.7 内
2、部排序方法的比较内部排序方法的比较10.8 外部排序外部排序 10.8.1 文件管理文件管理 10.8.2 外部排序外部排序 10.8.3 多路归并排序多路归并排序 10.8.4 置换选择排序置换选择排序 *10.8.5 最佳归并树最佳归并树 *10.8.6 磁带排序磁带排序第2页，共91页。主要内容知识点知识点1、排序的定义，排序可以看作是线性表的一种操作排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、插入排序（直接插入、对分插入对分插入、二路插入、表插入、希尔插入排序）。、二路插入、表插
3、入、希尔插入排序）。4、交换排序（冒泡排序、交换排序（冒泡排序、快速排序快速排序）。）。5、选择排序（简单选择排序、树形选择排序、选择排序（简单选择排序、树形选择排序、堆排序堆排序）。）。6、归并排序、基数排序。、归并排序、基数排序。7、外部排序、外部排序重点难点重点难点1、各种排序所基于的基本思想。、各种排序所基于的基本思想。2、排序性能的分析，是否是稳定排序。、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序折半插入、希尔排序。4、快速排序快速排序。5、堆排序堆排序。6、败者树、置换选择排序、败者树、置换选择排序、最佳归并树最佳归并树。7、对每种排序方法的学习，能举一反三。、对每种排
4、序方法的学习，能举一反三。第3页，共91页。基本概念 排序：排序：假设含假设含n个记录的序列为个记录的序列为R1,R2,Rn，其相应的关键字序列为其相应的关键字序列为 K1,K2,Kn，这些关键字相互之间可以进行比较，即在它们之间这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系存在着这样一个关系Ks1Ks2Ksn，按此固有关，按此固有关系将系将n个记录的序列重新排列为个记录的序列重新排列为 Rs1,Rs2,Rsn 的操的操作称作排序。作称作排序。第4页，共91页。基本概念稳定排序稳定排序：若若Ki为关键字，为关键字，Ki=Kj（ij），且在排序前），且在排序前的序列中的序列中Ri
5、领先于领先于Rj。经过排序后，。经过排序后，Ri与与Rj的相对次序的相对次序保持不变（即保持不变（即Ri仍领先于仍领先于Rj），则称这种排序方法是），则称这种排序方法是稳稳定的定的，否则称之为，否则称之为不稳定的。不稳定的。内部排序内部排序 ：若整个排序过程不需要访问外存便能完成，：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序则称此类排序问题为内部排序 外部排序外部排序：若参加排序的记录数量很大，整个序列的：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问排序过程不可能一次在内存中完成，则称此类排序问题为外部排序题为外部排序 第5页，共91
6、页。排序的类型定义#define n 待排序记录的个数待排序记录的个数typedef struct int key;AnyType other;记录其它数据域记录其它数据域 RecType;RecType Rn+1;第6页，共91页。基本思想基本思想：假定第一个记录有序假定第一个记录有序，从第从第2 2个记录开始，将个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。至所有记录都进入有序序列中。插入排序 插入排序种类插入排序种类：直接插入排序直接插入排序 折半插入排序折半插入排序 二路插入排序二路插入
7、排序 表插入排序表插入排序 希尔排序希尔排序 第7页，共91页。直接插入排序基本思想基本思想：将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i 第8页，共91页。示例初始关键字序列：51 33 62 96 87 17 28 51i=2(33)33 51 62 96 87 17 28 51i=3(62)33 51 62 96 87 17 28 51i=4(96)33 51 62 96 87 17 28 51i=5(87)33 51 62 87 96 17 28 51i=6(17)17 33 51 62 87 96 28 51i=7(28)17 2
8、8 33 51 62 87 96 51i=8(51)17 28 33 51 51 62 87 96第9页，共91页。一趟直接插入排序算法void StrOnePass(RecType R，int i)已知已知R1.i-1中的记录按关键字非递减有序排列，本算法中的记录按关键字非递减有序排列，本算法 插入插入Ri,使使R1.i中的记录按关键字非递减有序排列中的记录按关键字非递减有序排列 R0=Ri;j=i-1;将待排序记录放进监视哨将待排序记录放进监视哨 x=R0.key;从后向前查找插入位置，将大于待排序记录向后移动从后向前查找插入位置，将大于待排序记录向后移动 while(x Rj.key)R
9、j+1=Rj;j-;记录后移记录后移 Rj+1=R0;将待排序记录放到合适位置将待排序记录放到合适位置 StrOnePass第10页，共91页。直接插入排序算法void StrInsSort1(RecType R，int n)本算法对本算法对R1.n进行直接插入排序进行直接插入排序 for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 StrOnePass(R，i)；第11页，共91页。直接插入排序性能分析 最好情况最好情况比较次数为n1次移动次数为2（n1）次w最坏情况最坏情况比较次数为 =(n+2)(n-1)/2 n2ii移动次数为 =(n+4)(n-1)/2 n2)21(i
10、i第12页，共91页。折半插入排序折半插入排序void BinsSort(RecType R，int n)对对R1.n进行折半插入排序进行折半插入排序 for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 R0=Ri;将待排记录将待排记录Ri暂存到暂存到R0 low=1;high=i-1;设置折半查找的范围设置折半查找的范围 Rlow.high while(low=high)m=(low+high)/2;折半折半 if(R0.keyhigh;j-)Rj+1=Rj;记录后移记录后移 Rhigh+1=R0;插入插入 forBinsSort第13页，共91页。折半插入排序性能分析折半插
11、入排序性能分析 减少了比较次数，移动次数不变。时间复杂度仍为O（n2）。第14页，共91页。在对一组记录在对一组记录（5454，3838，9696，2323，1515，7272，6060，4545，8383）进行直接排序时，当把第进行直接排序时，当把第7 7个记录个记录6060插入到有插入到有序表时，为寻找插入位置需比较多少次序表时，为寻找插入位置需比较多少次第15页，共91页。二路插入排序二路插入排序 对折半插入排序改进，减少了移动记录的次数，但它对折半插入排序改进，减少了移动记录的次数，但它要借助要借助n个记录的辅助空间，即其空间复杂度为个记录的辅助空间，即其空间复杂度为O（n）。）。基本
12、思想：另设一数组基本思想：另设一数组d，将，将R1赋值给赋值给d1，并将，并将d1看作排好序的中间记录，从第二个记录起依次将看作排好序的中间记录，从第二个记录起依次将关键字小于关键字小于d1的记录插入的记录插入d1之前的有序序列，将之前的有序序列，将关键字大于关键字大于d1的记录插入的记录插入d1之后的有序序列。之后的有序序列。借助两个变量借助两个变量first和和final来指示排序过程中有序序列来指示排序过程中有序序列第一个记录和最后一个记录在第一个记录和最后一个记录在d中的位置。中的位置。第16页，共91页。初始关键字序列：初始关键字序列：51 33 62 96 87 17 28 51
13、i=1 51 firstfinali=2 51 33 final firsti=3 51 62 33 final firsti=4 51 62 96 33 final firsti=5 51 62 87 96 33 final firsti=6 51 62 87 96 17 33 final first i=7 51 62 87 96 17 28 33 final first i=8 51 51 62 87 96 17 28 33 final first 第17页，共91页。二路插入排序算法二路插入排序算法 void BiInsertSort(RecType R，int n)二路插入排序的算法
14、二路插入排序的算法 int dn+1;辅助存储辅助存储 d1=R1;first=1;final=1;for(i=2;i=d1.key)插入后部插入后部 low=1;high=final;while(low=high)折半查找插入位置折半查找插入位置 m=(low+high)/2;if(Ri.key=high+1;j-)dj+1=dj;移动元素移动元素 dhigh+1=Ri;final+;插入有序位置插入有序位置 第18页，共91页。else if(first=1)插入前部插入前部 first=n;dn=Ri;else low=first;high=n;while(low=high)m=(low
15、+high)/2;if(Ri.key dm.key)high=m-1;else low=m+1;while for(j=first;j=high;j+)dj-1=dj;移动元素移动元素 dhigh=Ri;first-;if if /for 第19页，共91页。表插入排序表插入排序 静态链表静态链表#define n 待排序记录的个数待排序记录的个数 typedef struct int key;AnyType other;记录其他数据域记录其他数据域 int next;STListType;STListType SLn+1;第20页，共91页。表插入排序算法表插入排序算法 void ListI
16、nsSort(STListType SL,int n)对记录序列对记录序列SL1.n作表插入排序。作表插入排序。SL0.key=MAXINT;SL0.next=1;SL1.next=0;for(i=2;i=n;i+)查找插入位置查找插入位置 j=0;for(k=SL0.next;SLk.key=SLi.key;)j=k,k=SLk.next;SLj.next=i;SLi.next=k;结点结点i插入在结点插入在结点j和结点和结点k之间之间 for ListInsSort第21页，共91页。表物理排序表物理排序void Arrange(STListType SL，int n)调整静态链表调整静态
17、链表SL中各结点的指针值，使记录按关键字有序排列中各结点的指针值，使记录按关键字有序排列 p=SL0.next;p指示第一个记录的当前位置指示第一个记录的当前位置 for(i=1;in;i+)SL1.i-1 记录已按关键字有序，第记录已按关键字有序，第i个记录的当前位置应不小于个记录的当前位置应不小于i while(p=1;d=d/2)for(i=1+d;i0&R0.keyaj+1），则将其交换，），则将其交换，最终达到有序化最终达到有序化 第28页，共91页。起泡排序示例初始关键字序列：初始关键字序列：51 33 62 96 87 17 28 51第一趟排序结果：第一趟排序结果：33 51
18、62 87 17 28 51 96 第二趟排序结果：第二趟排序结果：33 51 62 17 28 51 87 96 第三趟排序结果：第三趟排序结果：33 51 17 28 51 62 87 96 第四趟排序结果：第四趟排序结果：33 17 28 51 51 62 87 96 第五趟排序结果：第五趟排序结果：17 28 33 51 51 62 87 96 第六趟排序结果：第六趟排序结果：17 28 33 51 51 62 87 96 第29页，共91页。void BubbleSort(RecType R，int n)起泡排序起泡排序 i=n;i 指示无序序列中最后一个记录的位置指示无序序列中最后
19、一个记录的位置 while(i1)lastExchange=1;记最后一次交换发生的位置记最后一次交换发生的位置 for(j=1;jRj+1.key）temp=Rj；Rj=Rj+1；Rj+1=temp；逆序时交换逆序时交换 lastExchange=j;if i=lastExchange;while 起泡排序算法第30页，共91页。一组关键字一组关键字（19,01,26,92,87,11,43,87,2119,01,26,92,87,11,43,87,21），），进行冒泡排序，进行冒泡排序，试列出每一趟排序后的关键字序列试列出每一趟排序后的关键字序列 第31页，共91页。快速排序 基本思想基本
20、思想：从待排序记录序列中任选取一个记：从待排序记录序列中任选取一个记录（通常可选第一个记录）的关键字作为录（通常可选第一个记录）的关键字作为枢轴枢轴（或支点），凡其关键字小于枢轴的记录均（或支点），凡其关键字小于枢轴的记录均移动至该记录之前，而关键字大于枢轴的记移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后。一趟快速排序后就录均移动至该记录之后。一趟快速排序后就将排序序列分成两部分，再分别对这两部分将排序序列分成两部分，再分别对这两部分递归递归快速排序。快速排序。由由Hoare(图灵奖获得者图灵奖获得者)1962年提出，被评为年提出，被评为20世世纪十大优秀算法之一纪十大优秀算法之
21、一。第32页，共91页。快速排序图示1n第33页，共91页。快速排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51R0=51 i(枢轴枢轴)jj向前扫描向前扫描 i j第一次交换之后：第一次交换之后：28 33 62 96 87 17 51 i ji向后扫描向后扫描 i j第二次交换之后：第二次交换之后：28 33 96 87 17 62 51 i jj向前扫描向前扫描 i j 第三次交换之后：第三次交换之后：28 33 17 96 87 62 51i向后扫描向后扫描 i j 第四次交换之后：第四次交换之后：28 33 17 87 96 62 51j向前扫描向
22、前扫描 i j 完成一趟排序：完成一趟排序：28 33 17 51 87 96 62 51 ij 第34页，共91页。快速排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51一趟排序之后一趟排序之后：28 33 17 51 87 96 62 51 分别进行快速排序：分别进行快速排序：17 28 33 结束结束 结束结束 51 62 87 96 51 62 结束结束 结束结束有序序列：有序序列：17 28 33 51 51 62 87 96第35页，共91页。快速排序算法int Partition(RecType R，int l，int h)交换记录子序列交换记录
23、子序列Rl.h中的记录，使枢轴记录到位并返回其所在位置中的记录，使枢轴记录到位并返回其所在位置 int i=l;j=h;用变量用变量i,j记录待排序记录首尾位置记录待排序记录首尾位置 R0=Ri;以子表的第一个记录作枢轴，将其暂存到记录以子表的第一个记录作枢轴，将其暂存到记录R0中中 x=Ri.key;用变量用变量x存放枢轴记录的关键字存放枢轴记录的关键字 while(ij)从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(i=x)j-;Ri=Rj;将比枢轴小的记录移到低端将比枢轴小的记录移到低端 while(ij&Ri.key=x)i+;Rj=Ri;将比枢轴大的记录移到高端将
24、比枢轴大的记录移到高端 while Ri=R0;枢轴记录到位枢轴记录到位 return i;返回枢轴位置返回枢轴位置Partition 第36页，共91页。快速排序算法void QuickSort(RecType R，int s，int t)对记录序列对记录序列Rs.t进行快速排序进行快速排序 if(st)k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);if QuickSort 快速排序的快速排序的平均时间复杂度平均时间复杂度为为O（nlog2n）最差为最差为O(n2)第37页，共91页。对下列一组关键字对下列一组关键字（46,
25、58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果试写出快速排序的每一趟的排序结果 第38页，共91页。选择排序 基本思想基本思想：依次从待排序记录序列中选择出关键字值最：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、小（或最大）的记录、关键字值次之的记录、，并分别将它们定位到序列左侧（或右侧）的第并分别将它们定位到序列左侧（或右侧）的第1个位个位置、第置、第2 2个位置、个位置、，从而使待排序的记录序列成为，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。按关键字值
26、由小到大（或由大到小）排列的有序序列。选择排序种类选择排序种类：直接（简单）选择排序直接（简单）选择排序 树形选择排序树形选择排序 堆排序堆排序 第39页，共91页。直接选择排序 待排记录序列的状态为：待排记录序列的状态为：有序序列有序序列R1.i-1 无序序列无序序列 Ri.n并且有序序列中所有记录的关键字均小于无序序列中记录并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第的关键字，则第i趟直接选择排序是，从无序序列趟直接选择排序是，从无序序列Ri.nRi.n的的n-i+1n-i+1记录中选出关键字最小的记录加入有序序列记录中选出关键字最小的记录加入有序序列 第40页，共91
27、页。直接选择排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51 第一趟排序后：第一趟排序后：17 33 62 96 87 51 28 51 第二趟排序后：第二趟排序后：17 28 28 62 96 87 51 33 51 第三趟排序后：第三趟排序后：17 28 28 33 33 96 87 51 62 51第四趟排序后：第四趟排序后：17 28 28 33 33 51 87 96 62 51第五趟排序后：第五趟排序后：17 28 28 33 33 51 51 96 62 87第六趟排序后：第六趟排序后：17 28 28 33 33 51 51 62 96 87
28、第七趟排序后：第七趟排序后：17 28 28 33 33 51 51 62 87 96 第41页，共91页。直接选择排序算法void SelectSort(RecType R，int n)对记录序列对记录序列R1.n作直接选择排序。作直接选择排序。for(i=1;in;i+)选择第选择第i小的记录，并交换到位小的记录，并交换到位 k=i;假定第假定第i个元素的关键字最小个元素的关键字最小 for(j=i+1;j=n;j+)找最小元素的下标找最小元素的下标 if(Rj.keyRk.key)k=j;if(i!=k)RiRk;与第与第i个记录交换个记录交换 forSelectSort 直接选择排序的
29、平均时间复杂度平均时间复杂度为O（n2）记录移动次数记录移动次数最好情况最好情况：0 0 最坏情况最坏情况：3(n-1)3(n-1)比较次数比较次数（与初始状态无关）：（与初始状态无关）：)(21)(211nninni第42页，共91页。堆的定义：堆是满足下列性质的数列堆的定义：堆是满足下列性质的数列K1,K2,Kn：堆排序 12ii2iiKKKK或12ii2iiKKKK（i=1,2,n/2）若上述数列是堆，则若上述数列是堆，则K K1 1必是数列中的最小值或最大必是数列中的最小值或最大值，分别称作小顶堆或大顶堆（小堆或大堆）。值，分别称作小顶堆或大顶堆（小堆或大堆）。第43页，共91页。堆排
30、序示例 28 51 33 62 87 96 17 51 51 87 33 28 51 62 96 17 96，51，87，33，28，62，51，17 是大顶堆 例如：17，28，51，33，62，96，87，51 是小顶堆第44页，共91页。建立完全二叉树基本思想基本思想：先建一个堆，即先选得一个关：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中个记录交换，之后将序列中前前n1个个记录重新记录重新调整为一个堆（调堆的过程称为调整为一个堆（调堆的过程称为“筛选筛选”），），再将堆顶记录和第再将堆顶记录和第n1个
31、记录交换，如此反复个记录交换，如此反复直至排序结束。直至排序结束。堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？成为一个新的堆？第45页，共91页。第二个问题解决方法第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，与其中小者
32、进行交换；重复上述操作，直至叶子结点，将得到新的堆将得到新的堆第一个问题解决方法第一个问题解决方法方法：把整个数组方法：把整个数组R1到到Rn调整为一个大根堆，调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为即把完全二叉树中以每一个结点为根的子树都调整为堆。所以需要将以序号为堆。所以需要将以序号为 n/2 ，n/2 1，1的结点作为根的子树调整为堆即可的结点作为根的子树调整为堆即可用筛选法调整堆用筛选法调整堆第46页，共91页。调整堆示例2851336287961751(a)堆2851336287965117(b)17与51交换后的情景第47页，共91页。调整堆示例515187
33、6228963317(d)28与87交换后调成的新堆3351516287962817(c)调整后的新堆第48页，共91页。建堆示例初始关键字序列：初始关键字序列：51，33，62，96，87，17，28，51为为例，其初始建大顶堆过程例，其初始建大顶堆过程 3362968728175151(a)4.8是堆，不调整3362968728175151(b)3.8是堆，不调整第49页，共91页。建堆示例3362968728175151(c)2.8不是堆，进行筛选不是堆，进行筛选9662518728175133(d)1.8不是堆，进行筛选不是堆，进行筛选8762515128179633(e)建成的大顶堆
34、建成的大顶堆第50页，共91页。堆排序筛选算法void Sift(RecType R，int i，int m)假设假设Ri+1.m中各元素满足堆的定义，本算法调整中各元素满足堆的定义，本算法调整Ri使序列使序列 Ri.m中各元素满足堆的性质中各元素满足堆的性质 R0=Ri;for(j=2*i;j=m;j*=2)if(jm&Rj.keyRj+l.key)j+;沿大者（右）方向筛选沿大者（右）方向筛选 if(R0.key0;i-)把把R1.n建成大顶堆建成大顶堆 Sift(R,i,n);for(i=n;i1;i-)输出并调堆输出并调堆 R1Ri;Sift(R,1,i-1);将将R1.i-1重新调整
35、为大顶堆重新调整为大顶堆 forHeapSort 堆排序的堆排序的时间复杂度时间复杂度为为O（nlog2n）第52页，共91页。时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn)建初始堆时间建初始堆时间：调用调用SIFT 过程过程 n/2 次，每次以次，每次以Ri为根的子树调整为堆。为根的子树调整为堆。具有具有n个结点的完全二叉树深度是个结点的完全二叉树深度是h=logn +1,第第i层结点个数至多为层结点个数至多为 2 i-1。SIFT对深度为对深度为k的完全二叉树进行比较的关键字次数至多为的完全二叉树进行比较的关键字次数至多为2(k-1)，因此比较，因此比较总次数不超过
36、总次数不超过C1(n)2 i-1*2(h-1)=2 h-1+2 h-2*2+2 h-3*3+2*(h-1)=2*2(log 2n)+1=4n重新建堆时间：重新建堆时间：排序过程中重新建堆比较总次数不超过排序过程中重新建堆比较总次数不超过C2(n)=2*(log n-1 +log n-2+log 2 )2n log n =O(n log n)lhi1第53页，共91页。已知一组关键字已知一组关键字（46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出堆排序建初始堆和排序的过程试写出堆排序建初始堆和排序的过程 第54页，共91页。归并排序 基本思想基
37、本思想：将一个具有将一个具有n个待排序记录的个待排序记录的序列看成是序列看成是n个长度为个长度为1的有序序列，然后进行两的有序序列，然后进行两两归并，得到两归并，得到n/2 个长度为个长度为2的有序序列，再的有序序列，再进行两两归并，得到进行两两归并，得到n/4 个长度为个长度为4的有序的有序序列，如此重复，直至得到一个长度为序列，如此重复，直至得到一个长度为n的有的有序序列为止序序列为止 第55页，共91页。归并排序示例二趟归并排序后二趟归并排序后：33 51 62 96 117 28 87 初始关键字序列初始关键字序列：51 33 62 96 87 17 28 一趟归并排序后一趟归并排序后
38、：33 51 62 96 117 87 28 三趟归并排序后三趟归并排序后：17 28 33 51 62 87 96 第56页，共91页。一趟归并排序算法void Merge(RecType R,RecType R1,int i,int l,int h)将有序的将有序的Ri.l和和Rl+1.h归并为有序的归并为有序的R1i.h for(j=l+1,k=i;i=l&j=h;k+)R中记录由小到大地并入中记录由小到大地并入R1 if(Ri.key=Rj.key)R1k=Ri+;else R1k=Rj+;if(i=l)R1k.h=Ri.l;将剩余的将剩余的Ri.l复制到复制到R1 if(j=h)R1
39、k.h=Rj.h;将剩余的将剩余的Rj.h复制到复制到R1 Merge第57页，共91页。归并排序算法void Msort(RecType R,RecType R1,int s,int t)将将Rs.t进行进行2-路归并排序为路归并排序为R1s.t if(s=t)R1s=Rs;else m=(s+t)/2;将将Rs.t平分为平分为Rs.m和和Rm+1.t Msort(R,R2,s,m);递归地将递归地将Rs.m归并为有序的归并为有序的R2s.m Msort(R,R2,m+1,t);递归地递归地Rm+1.t归并为有序的归并为有序的R2m+1.t Merge(R2,R1,s,m,t);将将R2s.
40、m和和R2m+1.t归并到归并到R1s.t ifMSort第58页，共91页。归并排序算法void MergeSort(RecType R,int n)对记录序列对记录序列R1.n作作2-路归并排序。路归并排序。MSort(R,R,1,n);MergeSort归并排序的设计复杂度为归并排序的设计复杂度为O(nlogn)第59页，共91页。分配排序 基本思想基本思想：利用关键字的结构，通过“分配”和“收集”的办法来实现排序 分配排序可分为桶排序和基数排序两类 第60页，共91页。桶排序桶排序（桶排序（Bucket Sort）也称箱排序（）也称箱排序（Bin Sort），其），其基本思想是：设置若
41、干个桶，依次扫描待排序记录基本思想是：设置若干个桶，依次扫描待排序记录R1.n，把关键字等于，把关键字等于k的记录全部都装到第的记录全部都装到第k个桶里个桶里（分配），然后，按序号依次将各非空的桶首尾连接起（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。来（收集）。第61页，共91页。基数排序基数排序 基数排序就是一种借助就是一种借助“多关键字排序多关键字排序”的思想来的思想来实现实现“单关键字排序单关键字排序”的算法的算法 假设有假设有n个记录待排序序列个记录待排序序列 R1,R2,，Rn，每个记，每个记录录Ri中含有中含有d个关键字个关键字(Ki0,Ki1,Kid-1),则称上
42、述记录序则称上述记录序列对关键字列对关键字(Ki0,Ki1,Kid-1)有序是指：对于序列中任意有序是指：对于序列中任意两个记录两个记录Ri和和Rj(1ijn)都满足下列都满足下列(词典词典)有序关系：有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中其中K0被称为被称为“最主最主”位关键字，位关键字，Kd-1被称为被称为“最次最次”位位关键字。关键字。第62页，共91页。最高位优先最高位优先MSD法：先对法：先对K0进行排序，并按进行排序，并按K0的的不同值将记录序列分成若干子序列之后，分别对不同值将记录序列分成若干子序列之后，分别对K1进行排序，进行排序，依次类推，
43、直至最后对最次位，依次类推，直至最后对最次位关键字排序完成为止。关键字排序完成为止。最低位优先最低位优先LSD法：先对法：先对Kd-1进行排序，然后对进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字进行排序，依次类推，直至对最主位关键字K0排序完排序完成为止。排序过程中不需要根据成为止。排序过程中不需要根据“前一个前一个”关键字的关键字的排序结果，将记录序列分割成若干个排序结果，将记录序列分割成若干个(“前一个前一个”关键字关键字不同的不同的)子序列。子序列。实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:第63页，共91页。基数排序示例p3693671672392
44、37138230139第一次分配得到：第一次分配得到：B0.f230B0.eB7.f367167237B7.eB8.f138B8.eB9.f369239139B9.e第一次收集得到：第一次收集得到：p230367167237138369239139第64页，共91页。基数排序示例第二次分配得到：第二次分配得到：B3.f230237138239139B3.eB6.f367167369B6.e第二次收集得到：第二次收集得到：p230237138239139367167369第65页，共91页。基数排序示例第三次分配得到：第三次分配得到：B1.f138139167B1.eB2.f230237239B
45、2.eB3.f367369B3.e第三次收集之后便得到记录的有序序列：第三次收集之后便得到记录的有序序列：p138139167230237239367369 第66页，共91页。基数排序的类型定义#define n 待排序记录的个数待排序记录的个数typedef struct int keyd;关键字由关键字由d个分量组成个分量组成 int next;静态链域静态链域AnyType other;记录其他数据域记录其他数据域 SLRecType;SLRecType Rn+1;R1.n存放存放n个待排序记录个待排序记录typedef struct int f,e;队列的头、尾指针队列的头、尾指针
46、SLQueue;SLQueue Bm 用队列表示桶，共用队列表示桶，共m个个第67页，共91页。基数排序的算法int RadixSort(SLRecType R,int n)对对R1.n进行基数排序，返回收集用的链头指针进行基数排序，返回收集用的链头指针 for(i=1;i=0;j-)进行进行d趟排序趟排序 for(i=0;im;i+)初始化桶初始化桶 Bi.f=-1;Bi.e=-1;for while(p!=-1)一趟分配，一趟分配，按关键字的第按关键字的第j个分量进行分配个分量进行分配 k=Rp.keyj;k为桶的序号为桶的序号 if(Bk.f=-1)Bk.f=p;Bk为空桶，将为空桶，将
47、Rp链到桶头链到桶头 else RBk.e.next=p;将将Rp链到桶尾链到桶尾 Bk.e=p;修改桶的尾指针修改桶的尾指针 p=Rp.next;扫描下一个记录扫描下一个记录 while接下页接下页 第68页，共91页。基数排序的算法（续）接上页接上页 i=0;/一趟收集一趟收集 while(Bi.f=-1)i+;找第一个非空的桶找第一个非空的桶 t=Bi.e;p=Bi.f p为收集链表的头指针，为收集链表的头指针，t为尾指针为尾指针 while(im-1)i+;取下一个桶取下一个桶 if(Bi.f!=-1)Rt.next=Bi.f;t=Bi.e;连接非空桶连接非空桶 while Rt.ne
48、xt=-1;本趟收集完毕，将链表的终端结点指针置空本趟收集完毕，将链表的终端结点指针置空 for return p;RadixSort第69页，共91页。基数排序的性能分析基数排序的时间复杂度是基数排序的时间复杂度是O(d*(rd+n)。当当n较小、较小、d较大时，基数排序并不合适。较大时，基数排序并不合适。只有当只有当n较大、较大、d较小时，特别是记录的信息量较大时，基较小时，特别是记录的信息量较大时，基数排序最为有效。数排序最为有效。基数排序存储空间复杂度为基数排序存储空间复杂度为O（rd）。）。基数排序是稳定的基数排序是稳定的。第70页，共91页。已知已知8 8个记录，其关键字分别为个记
49、录，其关键字分别为(179(179，208208，306306，093093，859859，984984，271271，033)033)试用基数排序法实施排序，描述其排序过程试用基数排序法实施排序，描述其排序过程 第71页，共91页。排序方法排序方法平均时间平均时间最坏情况最坏情况辅助空间辅助空间稳定性稳定性直接插入排序直接插入排序O（n2）O（n2）O（1）稳定稳定起泡排序起泡排序O（n2）O（n2）O（1）稳定稳定直接选择排序直接选择排序O（n2）O（n2）O（1）不稳定不稳定希尔排序希尔排序O（n1.3）O（n1.3）O（1）不稳定不稳定快速排序快速排序O（nlog2n）O（n2）O（l
50、og2n）不稳定不稳定堆排序堆排序O（nlog2n）O（nlog2n）O（1）不稳定不稳定2-路归并排序路归并排序O（nlog2n）O（nlog2n）O（n）稳定稳定基数排序基数排序O(d*(rd+n)O(d*(rd+n)O(rd)稳定稳定内部排序方法的比较 第72页，共91页。结论（1）若）若n较小（如较小（如n50），可采用），可采用直接插入排序直接插入排序或或直接选直接选择排序择排序。（2）若待排序记录的初始状态已是按关键字）若待排序记录的初始状态已是按关键字基本有序基本有序，则，则选用选用直接插入排序直接插入排序或或起泡排序起泡排序为宜。为宜。（3）当）当n较大较大，若关键字有明显结构
