第10章数据结构排序课件.ppt

1、1第10章 排序 陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓2本章目录w 10.1 概述概述w 10.2 插入排序插入排序 n 10.2.1 直接插入排序直接插入排序 n 10.2.2 折半插入排序折半插入排序 *10.2.3 二路插入排序二路插入排序 *10.2.4 表插入排序表插入排序 n 10.2.5 希尔排序希尔排序w 10.3 交换排序交换排序 n 10.3.1 起泡排序起泡排序 n 10.3.2 快速排序快速排序w 10.4 选择排序选择排序 n10.4.1 直接选择排序直接选择排序 n10.4.2 树形选择排序树形选择排序n10.4.3 堆排序堆排序w 10.5 归并排序归并排序w 1

2、0.6 分配排序分配排序w 10.7 内部排序方法的比较内部排序方法的比较w 10.8 外部排序外部排序 n 10.8.1 文件管理文件管理 10.8.2 外部排序外部排序 10.8.3 多路归并排序多路归并排序 n 10.8.4 置换选择排序置换选择排序 *10.8.5 最佳归并树最佳归并树 *10.8.6 磁带排序磁带排序3主要内容w知识点知识点w1、排序的定义，排序可以看作是线性表的一种操作排序的定义，排序可以看作是线性表的一种操作w2、排序的分类，稳定排序与不稳定排序的定义。、排序的分类，稳定排序与不稳定排序的定义。w3、插入排序（直接插入、插入排序（直接插入、对分插入对分插入、二路插

3、入、表插入、希尔插、二路插入、表插入、希尔插入排序）。入排序）。w4、交换排序（冒泡排序、交换排序（冒泡排序、快速排序快速排序）。）。w5、选择排序（简单选择排序、树形选择排序、选择排序（简单选择排序、树形选择排序、堆排序堆排序）。）。w6、归并排序、基数排序。、归并排序、基数排序。w7、外部排序、外部排序w重点难点重点难点w1、各种排序所基于的基本思想。、各种排序所基于的基本思想。w2、排序性能的分析，是否是稳定排序。、排序性能的分析，是否是稳定排序。w3、折半插入、希尔排序折半插入、希尔排序。w4、快速排序快速排序。w5、堆排序堆排序。w6、败者树、置换选择排序、败者树、置换选择排序、最佳

4、归并树最佳归并树。w7、对每种排序方法的学习，能举一反三。、对每种排序方法的学习，能举一反三。4基本概念 w 排序：排序：假设含假设含n个记录的序列为个记录的序列为R1,R2,Rn，其相应的关键字序列为其相应的关键字序列为 K1,K2,Kn，这些关键字相互之间可以进行比较，即在它这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系们之间存在着这样一个关系Ks1Ks2Ksn，按此固有关系将按此固有关系将n个记录的序列重新排列为个记录的序列重新排列为 Rs1,Rs2,Rsn 的操作称作排序。的操作称作排序。5基本概念稳定排序稳定排序：若若Ki为关键字，为关键字，Ki=Kj（ij），且在）

5、，且在排序前的序列中排序前的序列中Ri领先于领先于Rj。经过排序后，。经过排序后，Ri与与Rj的相对次序保持不变（即的相对次序保持不变（即Ri仍领先于仍领先于Rj），则称这），则称这种排序方法是种排序方法是稳定的稳定的，否则称之为，否则称之为不稳定的。不稳定的。内部排序内部排序 ：若整个排序过程不需要访问外存便能完：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序成，则称此类排序问题为内部排序 外部排序外部排序：若参加排序的记录数量很大，整个序列：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排的排序过程不可能一次在内存中完成，则称此类排序问题为外

6、部排序序问题为外部排序 6排序的类型定义#define n 待排序记录的个数待排序记录的个数typedef struct int key;AnyType other;记录其它数据域记录其它数据域 RecType;RecType Rn+1;7基本思想基本思想：假定第一个记录有序假定第一个记录有序，从第从第2 2个记录开个记录开始，将待排序的记录插入到有序序列中，使有序序始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。列逐渐扩大，直至所有记录都进入有序序列中。插入排序 插入排序种类插入排序种类：直接插入排序直接插入排序 折半插入排序折半插入排序 二路插入排序二

7、路插入排序 表插入排序表插入排序 希尔排序希尔排序 8直接插入排序基本思想基本思想：将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i 9示例初始关键字序列：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 28 33 51 62 87

8、 96 51i=8(51)17 28 33 51 51 62 87 9610一趟直接插入排序算法void StrOnePass(RecType R，int i)已知已知R1.i-1中的记录按关键字非递减有序排列，本算法中的记录按关键字非递减有序排列，本算法 插入插入Ri,使使R1.i中的记录按关键字非递减有序排列中的记录按关键字非递减有序排列 R0=Ri;j=i-1;将待排序记录放进监视哨将待排序记录放进监视哨 x=R0.key;从后向前查找插入位置，将大于待排序记录向后移动从后向前查找插入位置，将大于待排序记录向后移动 while(x Rj.key)Rj+1=Rj;j-;记录后移记录后移 R

9、j+1=R0;将待排序记录放到合适位置将待排序记录放到合适位置 StrOnePass11直接插入排序算法void StrInsSort1(RecType R，int n)本算法对本算法对R1.n进行直接插入排序进行直接插入排序 for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 StrOnePass(R，i)；12直接插入排序性能分析w 最好情况最好情况比较次数为n1次移动次数为2（n1）次w最坏情况最坏情况比较次数为 =(n+2)(n-1)/2 n2ii移动次数为 =(n+4)(n-1)/2 n2)21(ii13折半插入排序折半插入排序w void BinsSort(RecT

10、ype R，int n)w 对对R1.n进行折半插入排序进行折半插入排序w for(i=2;i=n;i+)假定第一个记录有序假定第一个记录有序 w R0=Ri;将待排记录将待排记录Ri暂存到暂存到R0w low=1;high=i-1;设置折半查找的范围设置折半查找的范围 Rlow.highw while(low=high)w m=(low+high)/2;折半折半w if(R0.keyhigh;j-)Rj+1=Rj;记录后移记录后移w Rhigh+1=R0;插入插入w forw BinsSort14折半插入排序性能分析折半插入排序性能分析w 减少了比较次数，移动次数不变。w 时间复杂度仍为O（

11、n2）。15 在对一组记录在对一组记录（5454，3838，9696，2323，1515，7272，6060，4545，8383）进行直接排序时，当把第进行直接排序时，当把第7 7个记录个记录6060插入插入到有序表时，为寻找插入位置需比较多少到有序表时，为寻找插入位置需比较多少次次16二路插入排序二路插入排序w 对折半插入排序改进，减少了移动记录的次数，对折半插入排序改进，减少了移动记录的次数，但它要借助但它要借助n个记录的辅助空间，即其空间复杂个记录的辅助空间，即其空间复杂度为度为O（n）。）。w 基本思想：另设一数组基本思想：另设一数组d，将，将R1赋值给赋值给d1，并将并将d1看作排好

12、序的中间记录，从第二个记录看作排好序的中间记录，从第二个记录起依次将关键字小于起依次将关键字小于d1的记录插入的记录插入d1之前的之前的有序序列，将关键字大于有序序列，将关键字大于d1的记录插入的记录插入d1之之后的有序序列。后的有序序列。w 借助两个变量借助两个变量first和和final来指示排序过程中有序来指示排序过程中有序序列第一个记录和最后一个记录在序列第一个记录和最后一个记录在d中的位置。中的位置。17w 初始关键字序列：初始关键字序列：51 33 62 96 87 17 28 51 w i=1 51w firstfinalw i=2 51 33w final firstw i=3

13、 51 62 33w final firstw i=4 51 62 96 33w final firstw i=5 51 62 87 96 33w final firstw i=6 51 62 87 96 17 33w final first w i=7 51 62 87 96 17 28 33w final first w i=8 51 51 62 87 96 17 28 33w final first 18二路插入排序算法二路插入排序算法w void BiInsertSort(RecType R，int n)w 二路插入排序的算法二路插入排序的算法w int dn+1;辅助存储辅助存储w

14、d1=R1;first=1;final=1;w for(i=2;i=d1.key)插入后部插入后部w low=1;high=final;w while(low=high)折半查找插入位置折半查找插入位置w m=(low+high)/2;w if(Ri.key=high+1;j-)dj+1=dj;移动元素移动元素w dhigh+1=Ri;final+;插入有序位置插入有序位置w 19 else if(first=1)插入前部插入前部w first=n;dn=Ri;w else low=first;high=n;w while(low=high)w m=(low+high)/2;w if(Ri.k

15、ey dm.key)high=m-1;w else low=m+1;w whilew for(j=first;j=high;j+)dj-1=dj;w 移动元素移动元素w dhigh=Ri;first-;w ifw if w /for w 20表插入排序表插入排序w 静态链表静态链表w#define n 待排序记录的个数待排序记录的个数w typedef structw int key;w AnyType other;记录其他数据域记录其他数据域w int next;w STListType;w STListType SLn+1;21表插入排序算法表插入排序算法w void ListInsSor

16、t(STListType SL,int n)w 对记录序列对记录序列SL1.n作表插入排序。作表插入排序。w SL0.key=MAXINT;w SL0.next=1;SL1.next=0;w for(i=2;i=n;i+)查找插入位置查找插入位置w j=0;w for(k=SL0.next;SLk.key=SLi.key;)w j=k,k=SLk.next;w SLj.next=i;SLi.next=k;w 结点结点i插入在结点插入在结点j和结点和结点k之间之间w for w ListInsSort22表物理排序表物理排序w void Arrange(STListType SL，int n)w

17、 调整静态链表调整静态链表SL中各结点的指针值，使记录按关键字有序排列中各结点的指针值，使记录按关键字有序排列w p=SL0.next;p指示第一个记录的当前位置指示第一个记录的当前位置w for(i=1;in;i+)w SL1.i-1 记录已按关键字有序，第记录已按关键字有序，第i个记录的当前位置应不小于个记录的当前位置应不小于iw while(p=1;d=d/2)for(i=1+d;i0&R0.keyaj+1），则将其交），则将其交换，最终达到有序化换，最终达到有序化 29起泡排序示例初始关键字序列：初始关键字序列：51 33 62 96 87 17 28 51第一趟排序结果：第一趟排序结

18、果：33 51 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 30void 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 起泡排序算法31一组关键字一组关键字（19,01,26,92,87,11,43,87,2119,01,26,92,87,11,43,87,21），），进行冒泡排序，进行冒泡排序，试列出每一趟排序后的关键字序列试列出每一趟排序后的关键字序列 32快速排序 n基本思想基本思想：从待排序记录序列中任选取

20、一：从待排序记录序列中任选取一个记录（通常可选第一个记录）的关键字个记录（通常可选第一个记录）的关键字作为作为枢轴枢轴（或支点），凡其关键字小于枢（或支点），凡其关键字小于枢轴的记录均移动至该记录之前，而关键字轴的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后。一大于枢轴的记录均移动至该记录之后。一趟快速排序后就将排序序列分成两部分，趟快速排序后就将排序序列分成两部分，再分别对这两部分再分别对这两部分递归递归快速排序。快速排序。由由Hoare(图灵奖获得者图灵奖获得者)1962年提出，被评年提出，被评为为20世纪十大优秀算法之一世纪十大优秀算法之一。33快速排序图示1n34快

21、速排序示例初始关键字序列初始关键字序列：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向前扫描向前扫描 i j 完成一趟排序：完成一趟排序：28 33 17

22、51 87 96 62 51 ij 35快速排序示例初始关键字序列初始关键字序列：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 9636快速排序算法int Partition(RecType R，int l，int h)交换记录子序列交换记录子序列Rl.h中的记录，使枢轴记录到位并返回其所在位置中的记录，使枢轴记录到位并返回其所在位置

23、 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;将比枢轴大的记录移到高端将比枢轴大的记录移到高端 while Ri=R0;枢轴记录到位枢轴记录到位 return i;返

24、回枢轴位置返回枢轴位置Partition 37快速排序算法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)38对下列一组关键字对下列一组关键字（46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果试写出

25、快速排序的每一趟的排序结果 39选择排序 基本思想基本思想：依次从待排序记录序列中选择出关键：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的字值最小（或最大）的记录、关键字值次之的记录、记录、，并分别将它们定位到序列左侧，并分别将它们定位到序列左侧（或右侧）的第（或右侧）的第1个位置、第个位置、第2 2个位置、个位置、，从而使待排序的记录序列成为按关键字值由小从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。到大（或由大到小）排列的有序序列。选择排序种类选择排序种类：直接（简单）选择排序直接（简单）选择排序 树形选择排序树形选择排序 堆排序堆排

26、序 40直接选择排序 待排记录序列的状态为：待排记录序列的状态为：有序序列有序序列R1.i-1 无序序列无序序列 Ri.n并且有序序列中所有记录的关键字均小于无序序列并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第中记录的关键字，则第i趟直接选择排序是，从无序趟直接选择排序是，从无序序列序列Ri.nRi.n的的n-i+1n-i+1记录中选出关键字最小的记录记录中选出关键字最小的记录加入有序序列加入有序序列 41直接选择排序示例初始关键字序列初始关键字序列：51 33 62 96 87 17 28 51 第一趟排序后：第一趟排序后：17 33 62 96 87 51 28 51

27、第二趟排序后：第二趟排序后：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第七趟排序后：第七趟排序后：17 28 28 33 33 51 51 62 87 96 42直接选择排序算法void SelectSort(RecType R，int n)对

28、记录序列对记录序列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 直接选择排序的平均时间复杂度平均时间复杂度为O（n2）记录移动次数记录移动次数最好情况最好情况：0 0 最坏情况最坏情况：3(n-1)3(n-1)比较次数比较次数（与初始状态无关）：（与初始状态无关）：)

29、(21)(211nninni43堆的定义：堆是满足下列性质的数列堆的定义：堆是满足下列性质的数列K1,K2,Kn：堆排序 12ii2iiKKKK或12ii2iiKKKK（i=1,2,n/2）若上述数列是堆，则若上述数列是堆，则K K1 1必是数列中的最小值或最大必是数列中的最小值或最大值，分别称作小顶堆或大顶堆（小堆或大堆）。值，分别称作小顶堆或大顶堆（小堆或大堆）。44堆排序示例 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 是小顶

30、堆45建立完全二叉树基本思想基本思想：先建一个堆，即先选得一个：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中最后一个记录交换，之后将序列中前前n1个个记录重新调整为一个堆（调堆的过程称记录重新调整为一个堆（调堆的过程称为为“筛选筛选”），再将堆顶记录和第），再将堆顶记录和第n1个个记录交换，如此反复直至排序结束。记录交换，如此反复直至排序结束。堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后

31、，调整剩余元素，使之成为一个新的堆？成为一个新的堆？46第二个问题解决方法第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆将得到新的堆第一个问题解决方法第一个问题解决方法方法：把整个数组方法：把整个数组R1到到Rn调整为一个大根堆，调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为即把完全二叉树中以每一个结点为

32、根的子树都调整为堆。所以需要将以序号为堆。所以需要将以序号为 n/2 ，n/2 1，1的结点作为根的子树调整为堆即可的结点作为根的子树调整为堆即可用筛选法调整堆用筛选法调整堆47调整堆示例2851336287961751(a)堆2851336287965117(b)17与51交换后的情景48调整堆示例5151876228963317(d)28与87交换后调成的新堆3351516287962817(c)调整后的新堆49建堆示例初始关键字序列：初始关键字序列：51，33，62，96，87，17，28，51为为例，其初始建大顶堆过程例，其初始建大顶堆过程 3362968728175151(a)4.8

33、是堆，不调整3362968728175151(b)3.8是堆，不调整50建堆示例3362968728175151(c)2.8不是堆，进行筛选不是堆，进行筛选9662518728175133(d)1.8不是堆，进行筛选不是堆，进行筛选8762515128179633(e)建成的大顶堆建成的大顶堆51堆排序筛选算法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.ke

34、yRj+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重新调整为大顶堆重新调整为大顶堆 forHeapSort 堆排序的堆排序的时间复杂度时间复杂度为为O（nlog2n）53时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn)建初始堆时间建初始堆时间：调用调用SIFT 过程过程 n/2 次，每次以次，每次以Ri为根的子树调为根的子树调整为堆。具有整为堆。具有n个结点的完全二叉

35、树深度是个结点的完全二叉树深度是h=logn +1,第第i层结点个数层结点个数至多为至多为 2 i-1。SIFT对深度为对深度为k的完全二叉树进行比较的关键字次数至的完全二叉树进行比较的关键字次数至多为多为2(k-1)，因此比较总次数不超过，因此比较总次数不超过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

36、54 已知一组关键字已知一组关键字（46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出堆排序建初始堆和排序的过程试写出堆排序建初始堆和排序的过程 55归并排序 基本思想基本思想：将一个具有将一个具有n个待排序记录个待排序记录的序列看成是的序列看成是n个长度为个长度为1的有序序列，然后的有序序列，然后进行两两归并，得到进行两两归并，得到n/2 个长度为个长度为2的有的有序序列，再进行两两归并，得到序序列，再进行两两归并，得到n/4 个长个长度为度为4的有序序列，如此重复，直至得到一的有序序列，如此重复，直至得到一个长度为个长度为n的有序序列为止的

37、有序序列为止 56归并排序示例二趟归并排序后二趟归并排序后：33 51 62 96 117 28 87 初始关键字序列初始关键字序列：51 33 62 96 87 17 28 一趟归并排序后一趟归并排序后：33 51 62 96 117 87 28 三趟归并排序后三趟归并排序后：17 28 33 51 62 87 96 57一趟归并排序算法void Merge(RecType R,RecType R1,int i,int l,int h)w 将有序的将有序的Ri.l和和Rl+1.h归并为有序的归并为有序的R1i.hw for(j=l+1,k=i;i=l&j=h;k+)w R中记录由小到大地并入

38、中记录由小到大地并入R1w if(Ri.key=Rj.key)R1k=Ri+;w else R1k=Rj+;w if(i=l)R1k.h=Ri.l;将剩余的将剩余的Ri.l复制到复制到R1w if(j=h)R1k.h=Rj.h;将剩余的将剩余的Rj.h复制到复制到R1w Merge58归并排序算法wvoid Msort(RecType R,RecType R1,int s,int t)w 将将Rs.t进行进行2-路归并排序为路归并排序为R1s.tw if(s=t)R1s=Rs;w elsew m=(s+t)/2;将将Rs.t平分为平分为Rs.m和和Rm+1.tw Msort(R,R2,s,m)

39、;递归地将递归地将Rs.m归并为有序的归并为有序的R2s.mw Msort(R,R2,m+1,t);递归地递归地Rm+1.t归并为有序的归并为有序的R2m+1.tw Merge(R2,R1,s,m,t);将将R2s.m和和R2m+1.t归并到归并到R1s.tw ifwMSort59归并排序算法wvoid MergeSort(RecType R,int n)w 对记录序列对记录序列R1.n作作2-路归并排序。路归并排序。w MSort(R,R,1,n);wMergeSortw归并排序的设计复杂度为归并排序的设计复杂度为O(nlogn)60分配排序 基本思想基本思想：利用关键字的结构，通过“分配”

40、和“收集”的办法来实现排序 分配排序可分为桶排序和基数排序两类 61桶排序桶排序（桶排序（Bucket Sort）也称箱排序（）也称箱排序（Bin Sort），），其基本思想是：设置若干个桶，依次扫描待排序其基本思想是：设置若干个桶，依次扫描待排序记录记录R1.n，把关键字等于，把关键字等于k的记录全部都装到的记录全部都装到第第k个桶里（分配），然后，按序号依次将各非空个桶里（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。的桶首尾连接起来（收集）。62基数排序基数排序 基数排序就是一种借助就是一种借助“多关键字排序多关键字排序”的思的思想来实现想来实现“单关键字排序单关键字排序”的

41、算法的算法 假设有假设有n个记录待排序序列个记录待排序序列 R1,R2,，Rn，每个记，每个记录录Ri中含有中含有d个关键字个关键字(Ki0,Ki1,Kid-1),则称上述记录序则称上述记录序列对关键字列对关键字(Ki0,Ki1,Kid-1)有序是指：对于序列中任意有序是指：对于序列中任意两个记录两个记录Ri和和Rj(1ijn)都满足下列都满足下列(词典词典)有序关系：有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中其中K0被称为被称为“最主最主”位关键字，位关键字，Kd-1被称为被称为“最次最次”位位关键字。关键字。63w 最高位优先最高位优先MSD法：先对法：先对

42、K0进行排序，并按进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别的不同值将记录序列分成若干子序列之后，分别对对K1进行排序，进行排序，依次类推，直至最后对最次，依次类推，直至最后对最次位关键字排序完成为止。位关键字排序完成为止。w 最低位优先最低位优先LSD法：先对法：先对Kd-1进行排序，然后对进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据排序完成为止。排序过程中不需要根据“前一前一个个”关键字的排序结果，将记录序列分割成若干关键字的排序结果，将记录序列分割成若干个个(“前一个前一个”关

43、键字不同的关键字不同的)子序列。子序列。实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:64基数排序示例p369367167239237138230139第一次分配得到：第一次分配得到：B0.f230B0.eB7.f367167237B7.eB8.f138B8.eB9.f369239139B9.e第一次收集得到：第一次收集得到：p23036716723713836923913965基数排序示例第二次分配得到：第二次分配得到：B3.f230237138239139B3.eB6.f367167369B6.e第二次收集得到：第二次收集得到：p2302371382391393671673

44、6966基数排序示例第三次分配得到：第三次分配得到：B1.f138139167B1.eB2.f230237239B2.eB3.f367369B3.e第三次收集之后便得到记录的有序序列：第三次收集之后便得到记录的有序序列：p138139167230237239367369 67基数排序的类型定义w#define n 待排序记录的个数待排序记录的个数w typedef structw int keyd;关键字由关键字由d个分量组成个分量组成w int next;静态链域静态链域w AnyType other;记录其他数据域记录其他数据域w SLRecType;w SLRecType Rn+1;R1

45、.n存放存放n个待排序记录个待排序记录w typedef structw int f,e;队列的头、尾指针队列的头、尾指针w SLQueue;w SLQueue Bm 用队列表示桶，共用队列表示桶，共m个个68基数排序的算法w int RadixSort(SLRecType R,int n)w 对对R1.n进行基数排序，返回收集用的链头指针进行基数排序，返回收集用的链头指针w for(i=1;i=0;j-)进行进行d趟排序趟排序w for(i=0;im;i+)初始化桶初始化桶w Bi.f=-1;Bi.e=-1;forw while(p!=-1)一趟分配，一趟分配，按关键字的第按关键字的第j个分

46、量进行分配个分量进行分配w k=Rp.keyj;k为桶的序号为桶的序号w if(Bk.f=-1)Bk.f=p;Bk为空桶，将为空桶，将Rp链到桶头链到桶头w else RBk.e.next=p;将将Rp链到桶尾链到桶尾w Bk.e=p;修改桶的尾指针修改桶的尾指针w p=Rp.next;扫描下一个记录扫描下一个记录w whilew 接下页接下页w 69基数排序的算法（续）w 接上页接上页w i=0;/一趟收集一趟收集w while(Bi.f=-1)i+;找第一个非空的桶找第一个非空的桶w t=Bi.e;p=Bi.f p为收集链表的头指针，为收集链表的头指针，t为尾指针为尾指针w while(i

47、m-1)w i+;取下一个桶取下一个桶w if(Bi.f!=-1)Rt.next=Bi.f;t=Bi.e;连接非空桶连接非空桶 w whilew Rt.next=-1;本趟收集完毕，将链表的终端结点指针置空本趟收集完毕，将链表的终端结点指针置空w forw return p;w RadixSort70基数排序的性能分析w 基数排序的时间复杂度是基数排序的时间复杂度是O(d*(rd+n)。w 当当n较小、较小、d较大时，基数排序并不合适。较大时，基数排序并不合适。w 只有当只有当n较大、较大、d较小时，特别是记录的信息量较大时，较小时，特别是记录的信息量较大时，基数排序最为有效。基数排序最为有效

48、。w 基数排序存储空间复杂度为基数排序存储空间复杂度为O（rd）。）。w 基数排序是稳定的基数排序是稳定的。71已知已知8 8个记录，其关键字分别为个记录，其关键字分别为(179(179，208208，306306，093093，859859，984984，271271，033)033)试用基数排序法实施排序，描述其排序过程试用基数排序法实施排序，描述其排序过程 72排序方法排序方法平均时间平均时间最坏情况最坏情况辅助空间辅助空间稳定性稳定性直接插入排序直接插入排序O（n2）O（n2）O（1）稳定稳定起泡排序起泡排序O（n2）O（n2）O（1）稳定稳定直接选择排序直接选择排序O（n2）O（n2

49、）O（1）不稳定不稳定希尔排序希尔排序O（n1.3）O（n1.3）O（1）不稳定不稳定快速排序快速排序O（nlog2n）O（n2）O（log2n）不稳定不稳定堆排序堆排序O（nlog2n）O（nlog2n）O（1）不稳定不稳定2-路归并排序路归并排序O（nlog2n）O（nlog2n）O（n）稳定稳定基数排序基数排序O(d*(rd+n)O(d*(rd+n)O(rd)稳定稳定内部排序方法的比较 73结论w（1）若）若n较小（如较小（如n50），可采用），可采用直接插入排序直接插入排序或或直接选择排序直接选择排序。w（2）若待排序记录的初始状态已是按关键字）若待排序记录的初始状态已是按关键字基本有

50、基本有序序，则选用，则选用直接插入排序直接插入排序或或起泡排序起泡排序为宜。为宜。w（3）当）当n较大较大，若关键字有明显结构特征（如字符，若关键字有明显结构特征（如字符串、整数等），且关键字位数较少易于分解，采用串、整数等），且关键字位数较少易于分解，采用时间性能是线性的时间性能是线性的基数排序基数排序较好。若关键字无明显较好。若关键字无明显结构特征或取值范围属于某个无穷集合（例如实数结构特征或取值范围属于某个无穷集合（例如实数型关键字）时，应借助于型关键字）时，应借助于“比较比较”的方法来排序，的方法来排序，可采用时间复杂度为可采用时间复杂度为O（nlog2n）的排序方法：）的排序方法：快