数据结构第10章排序.pptx

2023/3/161第第1010章章 排排序序第1页/共127页2023/3/162本章目录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内部排序方法的比较10.8外部排序10.8.1文件管理10.8.2外部排序10.8.3多路归并排序10.8.4置换选择排序*10.8.5最佳归并树*10.8.6磁带排序第2页/共127页2023/3/163主要内容知识点1、排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。7、外部排序重点难点1、各种排序所基于的基本思想。2、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序。4、快速排序。5、堆排序。6、败者树、置换选择排序、最佳归并树。7、对每种排序方法的学习，能举一反三。第3页/共127页2023/3/164基本概念 排序：排序：假设含n个记录的序列为R1,R2,Rn，其相应的关键字序列为K1,K2,Kn，这些关键字相互之间可以进行比较，即在 它 们 之 间 存 在 着 这 样 一 个 关 系Ks1Ks2Ksn，按此固有关系将n个记录的序列重新排列为Rs1,Rs2,Rsn的操作称作排序。第4页/共127页2023/3/165基本概念稳定排序稳定排序：若Ki为关键字，Ki=Kj（ij），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。内部排序内部排序 ：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序 外部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为外部排序 第5页/共127页2023/3/166排序的类型定义#define n 待排序记录的个数typedef struct int key;AnyType other;记录其它数据域 RecType;RecType Rn+1;第6页/共127页2023/3/167基本思想基本思想：假定第一个记录有序，从第2 2个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。插入排序 插入排序种类插入排序种类：直接插入排序 折半插入排序 二路插入排序 表插入排序 希尔排序 第7页/共127页2023/3/168直接插入排序基本思想基本思想：将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i第8页/共127页2023/3/169示例初始关键字序列：5133629687172851i=2(33)3351629687172851i=3(62)3351629687172851i=4(96)3351629687172851i=5(87)3351628796172851i=6(17)1733516287962851i=7(28)1728335162879651i=8(51)1728335151628796第9页/共127页2023/3/1610一趟直接插入排序算法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-;记录后移 Rj+1=R0;将待排序记录放到合适位置 StrOnePass第10页/共127页2023/3/1611直接插入排序算法void StrInsSort1(RecType R，int n)本算法对R1.n进行直接插入排序 for(i=2;i=n;i+)假定第一个记录有序 StrOnePass(R，i)；第11页/共127页2023/3/1612直接插入排序性能分析w最坏情况最坏情况比较次数为 =(n+2)(n-1)/2 移动次数为=(n+4)(n-1)/2最好情况最好情况比较次数为n-1次移动次数为2（n-1）次第12页/共127页2023/3/1613直接插入排序的优缺点 直接插入排序直接插入排序算法简单算法简单，当待排序记录数量，当待排序记录数量n很小时，局部有序时，较为适用。很小时，局部有序时，较为适用。当当n很大时，其效率不高很大时，其效率不高。若对直接插入排序算法进行改进，可从减少若对直接插入排序算法进行改进，可从减少“比较比较”和和“移动移动”次数这两方面着手次数这两方面着手。折半存入排序折半存入排序、二路插入排序二路插入排序、表插入排序表插入排序、希尔排序希尔排序都是对直接插入排序的改进都是对直接插入排序的改进。第13页/共127页2023/3/1614折半插入排序voidBinsSort(RecTypeR，intn)对R1.n进行折半插入排序for(i=2;i=n;i+)假定第一个记录有序R0=Ri;将待排记录Ri暂存到R0low=1;high=i-1;设置折半查找的范围Rlow.highwhile(low=high)m=(low+high)/2;折半if(R0.keyhigh;j-)Rj+1=Rj;记录后移Rhigh+1=R0;插入forBinsSort第14页/共127页2023/3/1615折半插入排序性能分析减少了比较次数，移动次数不变。时间复杂度仍为O（n2）。第15页/共127页2023/3/1616 在对一组记录在对一组记录（5454，3838，9696，2323，1515，7272，6060，4545，8383）进行直接排序时，当把第进行直接排序时，当把第7 7个记录个记录6060插入到插入到有序表时，为寻找插入位置需比较多少次有序表时，为寻找插入位置需比较多少次自测题1第16页/共127页2023/3/1617二路插入排序对折半插入排序改进，减少了移动记录的次数，但它要借助n个记录的辅助空间，即其空间复杂度为O（n）。基本思想：另设一数组d，将R1赋值给d1，并将d1看作排好序的中间记录，从第二个记录起依次将关键字小于d1的记录插入d1之前的有序序列，将关键字大于d1的记录插入d1之后的有序序列。借助两个变量first和final来指示排序过程中有序序列第一个记录和最后一个记录在d中的位置。第17页/共127页2023/3/1618初始关键字序列：5133629687172851i=151firstfinali=25133finalfirsti=3516233finalfirsti=451629633finalfirsti=55162879633finalfirsti=6516287961733finalfirsti=751628796172833finalfirsti=85151628796172833finalfirst 第18页/共127页2023/3/1619二路插入排序算法voidBiInsertSort(RecTypeR，intn)二路插入排序的算法intdn+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+;插入有序位置第19页/共127页2023/3/1620elseif(first=1)插入前部first=n;dn=Ri;elselow=first;high=n;while(low=high)m=(low+high)/2;if(Ri.keydm.key)high=m-1;elselow=m+1;whilefor(j=first;j=high;j+)dj-1=dj;移动元素dhigh=Ri;first-;ifif/for第20页/共127页2023/3/1621表插入排序静态链表#definen待排序记录的个数typedefstructintkey;AnyTypeother;记录其他数据域intnext;STListType;STListTypeSLn+1;第21页/共127页2023/3/1622表插入排序算法voidListInsSort(STListTypeSL,intn)对记录序列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之间forListInsSort第22页/共127页2023/3/1623表物理排序voidArrange(STListTypeSL，intn)调整静态链表SL中各结点的指针值，使记录按关键字有序排列p=SL0.next;p指示第一个记录的当前位置for(i=1;in;i+)SL1.i-1记录已按关键字有序，第i个记录的当前位置应不小于iwhile(p=1;d=d/2)for(i=1+d;i0&R0.keyaj+1.key），则将其交换，最终达到有序化第29页/共127页2023/3/1630起泡排序示例初始关键字5133629687172851第一趟335162871728519696第四趟3317 285151628796第三趟3351172851628796第二趟3351621728518796第五趟17 28335151628796第六趟17 28335151628796第30页/共127页2023/3/1631void BubbleSort(RecType R，int n)起泡排序 i=n;i 指示无序序列中最后一个记录的位置 while(i1)LastExchange=1;记最后一次交换发生的位置 for(j=1;jRj+1.key)RjRj+1;逆序时交换 LastExchange=j;if i=LastExchange;while 起泡排序算法第31页/共127页2023/3/1632起泡排序性能分析平均时间复杂度：O(n2)第32页/共127页2023/3/1633一组关键字一组关键字（19,01,26,92,87,11,43,87,2119,01,26,92,87,11,43,87,21），），进行冒泡排序，进行冒泡排序，试列出每一趟排序后的关键字序列试列出每一趟排序后的关键字序列 自测题 3 冒泡排序示例第33页/共127页2023/3/1634快速排序 基本思想基本思想：从排序序列中任选一记录作为枢轴枢轴（或支点），凡其关键字小于枢轴关键字小于枢轴的记录均移动至该记录之前，而关键字的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后大于枢轴的记录均移动至该记录之后。一趟排序后“枢轴”到位，并将序列分成两部分，再分别对这两部分排序。由Hoare(图灵奖获得者)1962年提出，被评为20世纪十大优秀算法之一。第34页/共127页2023/3/1635快速排序图示不大于不小于1n枢轴第35页/共127页2023/3/1636快速排序示例初始关键字序列：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向前扫描 ij第三次交换之后：28 33 17 96 87 62 51i向后扫描 i j 第四次交换之后：28 33 17 87 96 62 51j向前扫描 i j 完成一趟排序：28 33 17 51 87 96 62 51 ij 第36页/共127页2023/3/1637快速排序示例初始关键字序列：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第37页/共127页2023/3/1638快速排序算法int Partition(RecType R，int l，int h)交换记录子序列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;将比枢轴大的记录移到高端 while Ri=R0;枢轴记录到位 return i;返回枢轴位置 Partition 第38页/共127页2023/3/1639快速排序算法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)第39页/共127页2023/3/1640对下列一组关键字（46,58,15,45,90,18,10,6246,58,15,45,90,18,10,62）试写出快速排序的每一趟的排序结果 自测题 4 快速排序示例第40页/共127页2023/3/1641设有顺序放置的设有顺序放置的n n个桶，每个个桶，每个桶中装有一粒砾石，每粒砾石的颜色桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排，是红、白、蓝之一。要求重新安排，使得红色砾石在前，白色砾石居中，使得红色砾石在前，白色砾石居中，蓝色砾石居后。对每粒砾石的颜色只蓝色砾石居后。对每粒砾石的颜色只能察看一次，且只允许交换操作来调能察看一次，且只允许交换操作来调整砾石的位置。整砾石的位置。【上海大学上海大学 1999 1999 二二 2(182(18分分)】算法举例算法举例 10.110.1 快速排序快速排序第41页/共127页2023/3/1642红、白、兰三色排序算法voidQkSort(rectyper,intn)inti=1,j=1,k=n;while(j=k)if(rj=1)当前元素是红色rirj;i+;j+;elseif(rj=2)j+;当前元素是白色else(rj=3当前元素是兰色rjrk;k-;QkSort第42页/共127页2023/3/1643冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学2001二.3(9分)】【北京邮电大学1992六(10分)】算法举例算法举例 10.2 10.2 双向双向冒泡排序第43页/共127页2023/3/1644voidBubbleSort2(inta,intn)相邻两趟向相反方向起泡的冒泡排序算法change=1;low=0;high=n-1;冒泡的上下界while(lowhigh&change)change=0;设不发生交换for(i=low;iai+1)aiai+1;change=1;有交换,修改标志changehigh-;修改上界for(i=high;ilow;i-)气泡下沉,小元素上浮(向左)if(aiai-1)aiai-1;change=1;有交换,修改标志changelow+;修改下界whileBubbleSort2 算法举例算法举例 10.2 10.2 双向双向冒泡排序的算法第44页/共127页2023/3/1645对给定关键字序号j(1jn)j(1jn)，要求在无序记录A1.nA1.n中找到关键字从小到大排在第j j位上的记录，写一个算法利用快速排序的划分思想实现上述查找。(要求用最少的时间和最少的空间)例如：给定无序关键字7,5,1,6,2,8,9,37,5,1,6,2,8,9,3，当j=4j=4时，找到的关键字应是5 5。【中科院研究生院20032003十二(15(15分)】【武汉理工大学20022002四.3(35/3.3(35/3分)】算法举例算法举例 10.3 10.3 快速排序第45页/共127页2023/3/1646intpartition(RecTypeA,int1,n)inti=1,j=n;x=Ai.key;i=1;while(ij)while(i=x)j-;if(ij)Ai+=Aj;while(ij&Ai.key=x)i+;if(ij)Aj-=Ai;returni;voidFind_j(RecTypeA,intn,intj)i=partition(A,1,n);while(i!=j)if(ij)i=quicksart(A,i+1,n);在后半部分继续进行划分elsei=quicksart(R,1,i-1);在前半部分继续进行划分算法举例算法举例 10.3 10.3 的算法第46页/共127页2023/3/1647选择排序 基本思想基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2 2个位置、，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。选择排序种类选择排序种类：直接（简单）选择排序 树形选择排序 堆排序第47页/共127页2023/3/1648直接选择排序 待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n有序序列中所有记录的关键字均小于无序序列中记录的关键字，第i趟直接选择排序是从无序序列Ri.nRi.n的n-i+1n-i+1记录中选出关键字最小的记录加入有序序列第48页/共127页2023/3/1649直接选择排序示例初始关键字序列：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第七趟排序后：17 28 28 33 33 51 51 62 87 96 第49页/共127页2023/3/1650直接选择排序算法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个记录交换 for SelectSort 直接选择排序的平均时间复杂度平均时间复杂度为O（n2）记录移动次数记录移动次数最好情况最好情况：0 0 最坏情况最坏情况：3(3(n-1)n-1)比较次数比较次数(与初始状态无关与初始状态无关):):第50页/共127页2023/3/1651 基基本本思思想想：对对n个个待待排排序序记记录录的的关关键键字字进进行行两两两两比比较较，从从中中选选出出 n/2 个个较较小小者者再再两两两两比比较较，直直到到选选出出关关键字最小的记录为止，此为键字最小的记录为止，此为一趟排序一趟排序。一一趟趟选选出出的的关关键键字字最最小小的的记记录录称称为为“冠冠军军”，而而“亚军亚军”是从与是从与“冠军冠军”比较失败的记录中找出比较失败的记录中找出。输输出出“冠冠军军”后后，将将（冠冠军军）叶叶子子结结点点关关键键字字改改为为最最大大，继继续续进进行行锦锦标标赛赛排排序序，直直到到选选出出关关键键字字次次小小的的记录为止，如此循环直到输出全部有序序列。记录为止，如此循环直到输出全部有序序列。树形选择排序(锦标赛排序)第51页/共127页2023/3/1652 对对关关键键字字序序列列72,73,71,23,94,16,05,68进进行行树树形形选择排序选择排序 树形选择排序(锦标赛排序)052305722316057273712394160568第52页/共127页2023/3/1653“亚亚军军”是是从从与与“冠冠军军”比比较较失失败败的的记记录录中中找找出出的的树形选择排序(锦标赛排序)1623167123166872737123941668亚军第53页/共127页2023/3/1654 n个个记记录录的的锦锦标标赛赛排排序序，每每选选择择一一个个记记录录需需 log2n 次比较，次比较，时间复杂度为时间复杂度为O(nlog2n)。缺点：需要缺点：需要较多的辅助存储空间较多的辅助存储空间；与与“最大值最大值”进行多次多余的比较进行多次多余的比较。对树形排序的改进是堆排序树形选择排序性能分析第54页/共127页2023/3/1655堆的定义：堆是满足下列性质的序列K1,K2,Kn：堆排序 或（i=1,2,n/2）若若上上述述序序列列是是堆堆，则则K K1 1必必是是序序列列中中的的最最小小值值或或最最大大值，分别称作小顶堆或大顶堆值，分别称作小顶堆或大顶堆 （小堆或大堆，小根堆或大根堆）。（小堆或大堆，小根堆或大根堆）。若若将将此此序序列列看看成成是是一一棵棵完完全全二二叉叉树树，则则堆堆或或是是空空树树或或是是满满足足下下列列特特性性的的完完全全二二叉叉树树：其其左左、右右子子树树分分别别是是堆堆，任任何何一一个结点的值不大于个结点的值不大于(或不小于或不小于)左左/右子女结点（若存在）的值右子女结点（若存在）的值第55页/共127页2023/3/1656堆排序示例96，51，87，33，28，62，51，17是大顶堆例如：17，28，51，33，62，96，87，51是小顶堆第56页/共127页2023/3/1657堆排序基基本本思思想想：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1个记录重新调整为一个堆（调堆的过程称为“筛选”），再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第57页/共127页2023/3/1658第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆第一个问题解决方法方法：把整个数组R1到Rn调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为堆。需要将以序号为 n/2 ，n/2 1，1的结点作为根的子树调整为堆用筛选法调整堆第58页/共127页2023/3/1659调整堆示例2851336287961751(a)堆2851336287965117(b)17与51交换后的情景第59页/共127页2023/3/1660调整堆示例5151876228963317(d)28与87交换后调成的新堆3351516287962817(c)调整后的新堆第60页/共127页2023/3/1661建堆示例初始关键字序列：51，33，62，96，87，17，28，51为例，其初始建大顶堆过程 3362968728175151(a)4.8是堆，不调整3362968728175151(b)3.8是堆，不调整第61页/共127页2023/3/1662建堆示例3362968728175151(c)2.8不是堆，进行筛选9662518728175133(d)1.8不是堆，进行筛选8762515128179633(e)建成的大顶堆第62页/共127页2023/3/1663堆排序筛选算法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重新调整为大顶堆 for HeapSort 堆排序的时间复杂度时间复杂度为O（nlog2n）第64页/共127页2023/3/1665时间复杂度：最坏情况下T(n)=O(nlogn)建初始堆时间：调用SIFT 过程 n/2 次，每次以Ri为根的子树调整为堆。具有n个结点的完全二叉树深度是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 )=1;i=i/2)if(R0.keyRi.key)Rj=Ri;j=i;else break;Rj=R0;sift(2)void HeapBuilder(RecType R,intn)for(i=2;i=n;i+)sift(R,i);第69页/共127页2023/3/1670归并排序 基基本本思思想想：将具有n个待排序记录的序列看成是n个长度为1的有序序列，进行两两归并，得到n/2 个长度为2的有序序列，再进行两两归并，得到n/4 个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止 第70页/共127页2023/3/1671归并排序示例二趟归并排序后：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 第71页/共127页2023/3/1672一趟归并排序算法voidMerge(RecTypeR,RecTypeR1,inti,intl,inth)将有序的Ri.l和Rl+1.h归并为有序的R1i.hfor(j=l+1,k=i;i=l&j=h;k+)R中记录由小到大地并入R1if(Ri.key=Rj.key)R1k=Ri+;elseR1k=Rj+;if(i=l)R1k.h=Ri.l;将剩余的Ri.l复制到R1if(j=h)R1k.h=Rj.h;将剩余的Rj.h复制到R1Merge第72页/共127页2023/3/1673归并排序算法voidMsort(RecTypeR,RecTypeR1,ints,intt)将Rs.t进行2-路归并排序为R1s.tif(s=t)R1s=Rs;elsem=(s+t)/2;将Rs.t平分为Rs.m和Rm+1.tMsort(R,R2,s,m);递归地将Rs.m归并为有序的R2s.mMsort(R,R2,m+1,t);递归地Rm+1.t归并为有序的R2m+1.tMerge(R2,R1,s,m,t);将R2s.m和R2m+1.t归并到R1s.tifMSort第73页/共127页2023/3/1674归并排序算法voidMergeSort(RecTypeR,intn)对记录序列R1.n作2-路归并排序。MSort(R,R,1,n);MergeSort归并排序的设计复杂度为O(nlogn)第74页/共127页2023/3/1675自测题 10.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A.起泡排序B.插入排序C.选择排序D.二路归并排序【2009年全国硕士研究生入学计算机学科专业基础综合试题】第75页/共127页2023/3/1676分配排序 基本思想基本思想：利用关键字的结构，通过“分配”和“收集”的办法来实现排序分配排序可分为桶排序和基数排序两类第76页/共127页2023/3/1677桶排序桶排序（Bucket Sort）也称箱排序（Bin Sort），其基本思想是：设置若干个桶，依次扫描待排序记录R1.n，把关键字等于k的记录全部都装到第k个桶里（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。第77页/共127页2023/3/1678基数排序基数排序基基数数排排序序就是一种借助“多关键字排序”的思想来实现“单关键字排序”的算法 假设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被称为“最次”位关键字。第78页/共127页2023/3/1679最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:第79页/共127页2023/3/1680基数排序示例p369367167239237138230139第一次分配得到：第一次分配得到：B0.f230B0.eB7.f367167237B7.eB8.f138B8.eB9.f369239139B9.e第一次收集得到：第一次收集得到：p230367167237138369239139第80页/共127页2023/3/1681基数排序示例第二次分配得到：B3.f230237138239139B3.eB6.f367167369B6.e第二次收集得到：p230237138239139367167369第81页/共127页2023/3/1682基数排序示例第三次分配得到：B1.f138139167B1.eB2.f230237239B2.eB3.f367369B3.e第三次收集之后便得到记录的有序序列：p138139167230237239367369第82页/共127页2023/3/1683基数排序的类型定义#definen待排序记录的个数typedefstructintkeyd;关键字由d个分量组成intnext;静态链域AnyTypeother;记录其他数据域SLRecType;SLRecTypeRn+1;R1.n存放n个待排序记录typedefstructintf,e;队列的头、尾指针SLQueue;SLQueueBm用队列表示桶，共m个第83页/共127页2023/3/1684基数排序的算法intRadixSort(SLRecTypeR,intn)对R1.n进行基数排序，返回收集用的链头指针for(i=1;i=0;j-)进行d趟排序for(i=0;im;i+)初始化桶Bi.f=-1;Bi.e=-1;forwhile(p!=-1)一趟分配，按关键字的第j个分量进行分配k=Rp.keyj;k为桶的序号if(Bk.f=-1)Bk.f=p;Bk为空桶，将Rp链到桶头elseRBk.e.next=p;将Rp链到桶尾Bk.e=p;修改桶的尾指针p=Rp.next;扫描下一个记录while接下页第84页/共127页2023/3/1685基数排序的算法（续）接上页i=0;/一趟收集while(Bi.f=-1)i+;找第一个非空的桶t=Bi.e;p=Bi.fp为收集链表的头指针,t为尾指针while(im-1)i+;取下一个桶if(Bi.f!=-1)Rt.next=Bi.f;t=Bi.e;连接非空桶whileRt.next=-1;本趟收集完毕，将链表的终端结点指针置空forreturnp;RadixSort第85页/共127页2023/3/1686基数排序的性能分析基数排序的时间复杂度是O(d*(rd+n)。当n较小、d较大时，基数排序并不合适。只有当n较大、d较小时，特别是记录的信息量较大时，基数排序最为有效。基数排序存储空间复杂度为O（rd）。基数排序是稳定的。第86页/共127页2023/3/1687自测题6已知已知8 8个记录，其关键字分别为个记录，其关键字分别为 (179(179，208208，306306，093093，859859，984984，271271，033)033)试用基数排序法实施排序，描述其排序过程试用基数排序法实施排序，描述其排序过程 第87页/共127页2023/3/1688排序方法排序方法平均时间平均时间最坏情况最坏情况辅助空间辅助空间稳定性稳定性直接插入排序直接插入排序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（log2n）不稳定不稳定堆排序堆排序O（nlog2n）O（nlog2n）O（1）不稳定不稳定2-路归并排序路归并排序O（nlog2n）O（nlog2n）O（n）稳定稳定基数排序基数排序O(d*(rd+n)O(d*(rd+n)O(rd)稳定稳定内部排序方法的比较 第88页/共127页2023/3/1689内部排序小结（1）若n较小（如n50），可采用直接插入排序直接插入排序或直接选择排序直接选择排序。（2）若待排序记录的初始状态已是按关键字基本有序，则选用直接插入排序直接插入排序或起泡排序起泡排序为宜。（3）当n较大，若关键字有明显结构特征（如字符串、整数等），且关键字位数较少易于分解，采用时间性能是线性的基数排序基数排序较好。若关键字无明显结构特征或取值范围属于某个无穷集合（例如实数型关键字）时，应借助于“比较”的方法来排序，可采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排快速排序、堆排序或归并排序序或归并排序。第89页/共127页2023/3/1690（4）对于以主关键字进行排序的记录序列，所用的排序方法是否稳定稳定无关紧要，而用次关键字进行排序的记录序列，应根据具体问题所需慎重选择排序方法及描述算法。（5）前面讨论的排序算法，大都是利用一维向量实现的。若记录本身信息量大，为避免移动记录耗费大量时间，可用链式存储结构链式存储结构。比如插入排序和归并排序都易于在链表上实现。但象快速排序和堆排序这样的排序算法，却难于在链表上实现，此时可以提取关键字建立索引表，然后对索引表进行排序。内部排序小结（续）第90页/共127页2023