数据结构C语言版第8章排序课件

《数据结构C语言版第8章排序课件》由会员分享，可在线阅读，更多相关《数据结构C语言版第8章排序课件（228页珍藏版）》请在装配图网上搜索。

1、排序第8章数据结构（C语言版）数据结构逻辑结构线性结构（线性表、栈、队、串、数组）非线性结构树结构图结构物理（存储结构）顺序结构链式结构数据运算插入运算删除运算修改运算查找运算排序运算掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用熟练掌握直接插入排序、折半插入排序、起泡排序、直接选择排序、快速排序的排序算法及其性能分析掌握希尔排序、归并排序、堆排序、基数排序的方法及其性能分析掌握外部排序方法中败者树的建立及归并方法，掌握置换-选择排序的过程和最佳归并树的构造方法。01OPTION02OPTION03OPTION04OPTIONtarget目标目 录 导 航8.18.28.38.48.

2、58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents1.什么是排序？将一组杂乱无章的数据按一定规律顺次排列起来。2.排序的目的是什么？存放在数据表中按关键字排序 便于查找！概述3.什么叫内部排序？什么叫外部排序？若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。概述4.排序算法的好坏如何衡量？概述空间效率占内存辅助空间的大小稳定性A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。时间效率排序速度（比较

3、次数与移动次数）记录序列以顺序表存储Typedef struct /定义每个记录（数据元素）的结构 KeyType key;/关键字 InfoType otherinfo;/其它数据项RedType;Typedef struct /定义顺序表的结构 RedType r MAXSIZE+1;/存储顺序表的向量/r0一般作哨兵或缓冲区 int length;/顺序表的长度SqList;#define MAXSIZE 20 /设记录不超过20个typedef int KeyType;/设关键字为整型量（int型）排序算法分类规则不同插入排序交换排序选择排序归并排序时间复杂度不同简单排序O(n2)先进

4、排序O(nlog2n)目 录 导 航8.18.28.38.48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents插入排序基本思想：即边插入边排序，保证子序列中随时都是排好序的 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。直接插入排序（基于顺序查找）不同的具体实现方法导致不同的算法描述折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）最简单的排序法！插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序

5、列有序。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】例（13，6，3，31，9，27，5，11）21212525494925*25*161608080 1 2 3 4 5 6暂暂存存2121i=2i=3i=5i=4i=625252549494925*25*25*494916161625*25*0808494

6、921212525494925*25*2121初态：1616494925*25*2525212116160808完成!将序列存入顺序表L中，将L.r0作为哨兵（21，25，49，25*，16，08）*表示后一个25直接插入排序有序序列R1.i-1Ri 无序序列 Ri.n插入排序的基本思想：有序序列R1.i无序序列 Ri+1.n插入排序的基本步骤：在R1.i-1中查找Ri的插入位置，R1.j.key Ri.key Rj+1.i-1.key；01OPTION02OPTION03OPTION将Rj+1.i-1中的所有记录均后移一个位置；将Ri 插入到Rj+1的位置上。从Ri-1向前进行顺序查找，监视

7、哨设置在R0if(L.ri.keyL.ri-1.key)R0=Ri;/设置“哨兵”Ri=Ri-1;for(j=i-2;R0.keyRj.key;-j)Rj+1=Rj;jRii-1插入位置直接插入排序关键字大于Ri.key的记录向后移动循环结束表明Ri的插入位置为 j+1L.rj+1=L.r0;/插入到正确位置直接插入排序void InsertSort(SqList L)int i,j;for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)/将L.ri插入有序子表 L.r0=L.ri;/复制为哨兵 L.ri=L.ri-1;for(j=i-2;L.r0.keyL.

8、rj.key;-j)L.rj+1=L.rj;/记录后移 L.rj+1=L.r0;/插入到正确位置 算法分析设对象个数为n，则执行n-1趟比较次数和移动次数与初始排列有关最好情况下：每趟只需比较 1 次，不移动 总比较次数为 n-121212525494925*25*16160808for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)最坏情况下：第 i 趟比较i次，移动i+1次21212525494925*25*16160808算法分析比较次数:移动次数:if(L.ri.keyL.ri-1.key)L.r0=L.ri;/复制为哨兵 L.ri=L.ri-1;L.

9、rj+1=L.r0;/插入到正确位置 若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况平均情况比较次数和移动次数为n2/4时间复杂度为 o(n2)空间复杂度为 o(1)是一种稳定的排序方法21212525494925*25*1616080821212525494925*25*161608080 1 2 3 4 5算法分析折半插入排序直接插入排序 减少关键字间的比较次数在插入 ri 时，利用折半查找法寻找 ri 的插入位置算法分析i=2折半插入排序i=3折半插入排序i=4折半插入排序i=5折半插入排序i=6折半插入排序void BInsertSort(SqList&L)for(i

10、=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high)m=(low+high)/2;if (L.r0.key=high+1;-j)L.rj+1=L.rj;L.rhigh+1=L.r0;/BInsertSort折半插入排序折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。算法分析它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。算法分析当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但

11、比其最好情况要差在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列减少了比较次数，但没有减少移动次数平均性能优于直接插入排序算法分析空间复杂度为 o(1)是一种稳定的排序方法时间复杂度为 o(n2)希尔排序算法思想的出发点：直接插入排序在基本有序时，效率较高在待排序的记录个数较少时，效率较高基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序子序列的构成不是简单地“逐段分割”将相隔某个增量

12、dk的记录组成一个子序列让增量dk逐趟缩短（例如依次取5,3,1）直到dk1为止。小元素跳跃式前移最后一趟增量为1时，序列已基本有序平均性能优于直接插入排序优点技巧38例：关键字序列 T=(49，38，65，97,76,13,27,49*，55,04）0123456789104938659776132749*5504初态：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 979713 27 0449*76 97 ridk 值较

13、大，子序列中对象较少，速度较快；dk 值逐渐变小，子序列中对象变多，但大多数对象已基本有序，所以排序速度仍然很快。希尔排序void ShellSort(SqList&L，int dlta，int t)/按增量序列dlta0t-1对顺序表L作Shell排序 for(k=0；kt；+k)ShellInsert(L，dltak)；/增量为dltak的一趟插入排序 /ShellSort希尔排序算法（主程序）dk值依次装在dltat中void ShellInsert(SqList&L，int dk)for(i=dk+1；i=L.length；+i)if(ri.key 0&(r0.keyrj.key);j

14、=j-dk)rj+dk=rj；rj+dk=r0；/对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子/开始将ri 插入有序增量子表/暂存在r0/关键字较大的记录在子表中后移/在本趟结束时将ri插入到正确位置希尔排序算法（其中某一趟的排序操作）时间复杂度是n和d的函数：空间复杂度为 o(1)是一种不稳定的排序方法算法分析O(n1.25）O（1.6n1.25）经验公式如何选择最佳d序列，目前尚未解决最后一个增量值必须为1，无除1以外的公因子不宜在链式存储结构上实现目 录 导 航8.18.28.38.48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents交

15、换排序基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。起泡排序O(n2)快速排序O(nlog2n)基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换起泡排序21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49起泡排序 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换，还可提前结束排序void main()int a11;/*a0不用，之用a1a10*/int i

16、,j,t;printf(nInput 10 numbers:n);for(i=1;i=10;i+)scanf(%d,&ai);printf(n);for(j=1;j=9;j+)for(i=1;iai+1)t=ai;ai=ai+1;ai+1=t;/交换for(i=1;i0)&(flag=1)flag=0;for(j=1;jL.rj+1.key)flag=1;x=L.rj;L.rj=L.rj+1;L.rj+1=x;/交换 /endif m-;/endwhile 起泡排序算法分析设对象个数为n比较次数和移动次数与初始排列有关只需 1趟排序，比较次数为 n-1，不移动 21212525494925*2

17、5*16160808while(m0)&(flag=1)flag=0;for(j=1;jL.rj+1.key)flag=1;x=L.rj;L.rj=L.rj+1;L.rj+1=x;最好情况下：21212525494925*25*16160808算法分析u时间复杂度为 o(n2)需 n-1趟排序，第i趟比较n-i次，移动3(n-i)次最坏情况下：u空间复杂度为 o(1)u是一种稳定的排序方法快速排序基本思想：任取一个元素(如第一个)为中心所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个21212525494925

18、*25*161608080 1 2 3 4 5212125*25*16162525161608084949pivotkey08082121pivotkeypivotkey快速排序25*25*2525494949490808161625*25*25252121快速排序0808161625*25*212125254949pivotkey 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0

19、1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949hig

20、hlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676

21、131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493

22、838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2

23、 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlo

24、w49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序 0 1 2 3 4 5 6 7 8493838656597977676131327274949highlow49界点快速排序A每一趟的子表的形成是采用从两头向中间交替式逼近法；B由于每趟中对各子表的操作都相似，可采用递归算法。void main()QSort(L,1,L.length);void QSort(SqList&L，

25、int low,int high)if (low high)pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high)快速排序int Partition(SqList&L，int low,int high)L.r0=L.rlow;pivotkey=L.rlow.key;while (low high)while(low=pivotkey)-high;L.rlow=L.rhigh;while(low high&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rl

26、ow=L.r0;return low;快速排序可以证明，平均计算时间是O(nlog2n)。算法分析实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n)。算法分析最坏从小到大排好序，递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列，必须经过 n-1 趟才能把所有对象定位，而且第 i 趟需要经过 n-i 次关键码比较才能找到第 i 个对象的安放位置。最好划分后，左侧右侧子序列的长度相同算法分析时间效率

27、：O(nlog2n)每趟确定的元素呈指数增加123稳 定 性：不稳定 可选任一元素为支点。空间效率：O（log2n）递归要用到栈空间目 录 导 航8.18.28.38.48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents选择排序基本思想：每一趟在后面 n-i+1个中选出关键码最小的对象,作为有序序列的第 i 个记录2125*i=125164908最小者 08交换21,0825160825*4921i=2最小者 16交换25,1649i=3081625*2521最小者 21交换49,21简单选择排序4925*25*25*25*0 1 2 3 4 5i=4081

28、62521最小者 25*无交换25*i=549最小者 25无交换2521160825160825*4921结果各趟排序后的结果简单选择排序void SelectSort(SqList&K)for(i=1;iL.length;+i)/在L.ri.L.length 中选择key最小的记录 k=i;for(j=i+1;j=L.length;j+)if(L.rj.key L.rk.key)k=j;if(k!=i)L.riL.rk;简单选择排序算法分析时间复杂度：O(n)空间复杂度：O(1)稳定比较次数：移动次数最好情况：0最坏情况：3(n-1)BAOBAODIAOCHABAODIAOWANGZHAOC

29、HALIUBAODIAOYANGXUEWANG树形选择排序DIAOCHADIAOWANGZHAOCHALIUDIAOYANGXUEWANG树形选择排序CHACHADIAOCHALIUDIAOWANGZHAOCHALIU*DIAOYANGXUEWANG树形选择排序DIAOLIUDIAOWANGZHAOLIU*DIAOYANGXUEWANG树形选择排序BIAOLIUDIAOZHAOLIUDIAOWANGZHAO*LIU*DIAOYANGXUEWANG树形选择排序改进：简单选择排序没有利用上次选择的结果，是造成速度慢的重要原因。如果，能够加以改进，将会提高排序的速度。3813762765499749

30、38651327133813选出最小者 13树形选择排序改进：简单选择排序没有利用上次选择的结果，是造成速度满的重要原因。如果，能够加以改进，将会提高排序的速度。381376276549974938651327133813选出次最小者，应利用上次比较的结果。从被 13 打败的结点 27、76、38 中加以确定。树形选择排序改进：简单选择排序没有利用上次选择的结果，是造成速度满的重要原因。如果，能够加以改进，将会提高排序的速度。381376276549974938651327133813选出次最小者，应利用上次比较的结果。从被 13 打败的结点 27、76、38 中加以确定。树形选择排序n个元素

31、的序列k1,k2,kn，当且仅当满足下列关系时，成为堆：堆排序什么是堆？如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。(87,78,53,45,65,09,31,17,23)(09,17,65,23,45,78,87,53,31)利用树的结构特征来描述堆，所以树只是作为堆的描述工具，堆实际是存放在线形空间中的。堆排序堆顶元素（根）为最小值或最大值小根堆 816 9 1 6 2 1110 5 4大根堆 1 6 812 916 2 11 5 14堆排序 816 9 10 6 2 111 5 4 1 9 810 616 2 11 54堆排序判定(80,75,40,62,73

32、,35,28,50,38,25,47,15)是否为堆807540627328355038254715完全二叉树大根堆堆排序将无序序列建成一个堆输出堆顶的最小（大）值使剩余的n-1个元素又调整成一个堆，则可得到n个元素的次小值重复执行，得到一个有序序列基本思想：如何建？如何调整？堆排序 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210如何将无序序列建成堆思考：有n 个结点的完全二叉树，最后一个分支结点的标号是多少？n/2 1 2 3 4 5 6 7 7060124030 810从第 n/2 个元素起，至第一个元素止，进行反复

33、筛选堆堆排序 70 1 60 240 4 30 5 12 3 8 610 7 1 2 3 4 5 6 7 3060 840701210无序序列建成堆1 30 1 60 240 4 70 5 3 610 7 8 12 1 2 3 4 5 6 7 3060124070810无序序列建成堆1 30 1 60 240 4 70 5 3 610 7 12 8 30 1 240 4 5 12 3 8 610 7 60 1 2 3 4 5 6 7 3060124070810无序序列建成堆2 70 1 2 3 4 5 6 7 3070124060810无序序列建成堆2 30 1 240 4 5 12 3 86

34、10 7 70 60 1 2 3 4 5 6 7 3070124060810无序序列建成堆3 1 70 240 4 60 5 12 3 8 610 7 30 1 2 3 4 5 6 7 7030124060810无序序列建成堆31240 4 60 5 12 3 8610 7 30 70 1 2 3 4 5 6 7 7060124030810无序序列建成堆3建堆完毕170240 4 5 12 3 8610 7 60 30输出堆顶元素后，以堆中最后一个元素替代之将根结点与左、右子树根结点比较，并与小者交换重复直至叶子结点，得到新的堆如何在输出堆顶元素后调整，使之成为新堆？筛选堆的重新调整 1 2

35、3 4 5 6 7 7060124030810堆的重新调整1 1 60 240 4 30 5 12 3 8 610 7 70堆的重新调整1 6040 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 510 17060124030810707010 601060堆的重新调整2 4010 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 560 160401210308107070 堆的重新调整2 4010 12 6010 7 1 2 3 4 5 6 7 3 6 2 30 58 18401210306010707060604 堆的重新调整2 3010 4 12

36、 6010 7 1 2 3 4 5 6 7 3 6 28 540 1403012108601070706060堆的重新调整3 3010 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 14030121086010707060604 堆的重新调整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 1830121086010707060604040堆的重新调整3 108 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新调整4 108 4 12 6010 7 1

37、 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新调整4 1030 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 18101230860107070606040403030堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 512 11210830860107070606040403030堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新调整5 1030 4

38、8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新调整5 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新调整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新调整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 1888308601070706060404030301

39、2121010算法分析时间效率：O(nlog2n)空间效率：O（1）稳 定 性：不稳定适用于n 较大的情况目 录 导 航8.18.28.38.48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents归并排序归并：将两个或两个以上的有序表组合成一个新有序表2-路归并排序排序过程初始序列看成n个有序子序列，每个子序列长度为1两两合并，得到 n/2 个长度为2或1的有序子序列再两两合并，重复直至得到一个长度为n的有序序列为止0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表0 1 2 3 4491365

40、9776780AB0 1 2 3 4 5 6 7 Cjk将两个顺序表合并成一个有序表7i0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cjk将两个顺序表合并成一个有序表7i0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cjk将两个顺序表合并成一个有序表713i0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表713490 1 2 3 44

41、913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两

42、个顺序表合并成一个有序表71349657680B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表7134965768097例初始关键字：49 38 65 97 76 13 27一趟归并后：38 49 65 97 13 76 27二趟归并后：38 49 65 97 13 27 76三趟归并后：13 27 38 49 65 76 97将两个顺序表合并成一个有序表算法分析时间效率：O(nlog2n)空间效率：O（n）稳 定 性：稳定以扑克牌排序为例。每张扑克牌有两个

43、“排序码”：花色和面值。其有序关系为：u 花色：u 面值：2 3 4 5 6 7 8 9 10 J Q K A 可以把所有扑克牌排成以下次序：2,A,2,A,2,A,2,A 花色相同的情况下，比较面值。算法分析目 录 导 航8.18.28.38.48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents基数排序前面的排序方法主要通过关键字值之间的比较和移动而基数排序不需要关键字之间的比较。对52张扑克牌按以下次序排序：2 3 A 2 3 A 2 3 A 2 3 A两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”多关键字排序最高位优先MSD(Most

44、Significant Digit first)最低位优先LSD(Least Significant Digit first)基数排序链式基数排序：用链表作存储结构的基数排序链式基数排序最高位优先法十进制数比较可以看作是一个多关键字排序先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序，就可以得到一个有序的序列。最高位优先法十位首先依据最低位排序码Kd对所有对象进行一趟排序。再依据次低位排序码Kd-1对上一趟排序结果排序。依次重复，直到依据排序

45、码K1最后一趟排序完成，就可以得到一个有序的序列。最低位优先法这种方法不需要再分组，而是整个对象组都参加排序最高位优先法先决条件：链式基数排序利用“分配”和“收集”对关键字进行排序过程首先对低位关键字排序，各个记录按照此位关键字的值分配到相应的序列里。按照序列对应的值的大小，从各个序列中将记录收集，收集后的序列按照此位关键字有序。在此基础上，对前一位关键字进行排序。知道各级关键字的主次关系知道各级关键字的取值范围初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f

46、3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：链式基数排序505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集链式基数排序008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配06

47、3083269278505589505008109930063269278083184589二趟收集链式基数排序设置10个队列，fi和ei分别头指针和尾指针链式基数排序步骤第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列重复执行d趟“分配”与“收集”每趟对 n 个记录进行“分配”，对rd个队列进行“收集”需要增加n+2rd个附加链

48、接指针。n个记录每个记录有 d 位关键字关键字取值范围rd(如十进制为10)算法分析时间效率：O(d(n+rd)d(n+rd)空间效率：O(n+rd)n+rd)稳 定 性：稳定目 录 导 航8.18.28.38.48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents由相对独立的两个步骤组成：外部排序的基本过程按可用内存大小,利用内部排序方法，构造若干个记录的有序子序列写入外存，通常称这些记录的有序子序列为“归并段”;通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。例如：假设有一个含10,000个记录的磁盘文件，而当前所

49、用的计算机一次只能对1,000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。假设进行2路归并(即两两归并)：最后一趟归并得到整个记录的有序序列。第三趟由 3 个归并段得到2个归并段;第二趟由 5 个归并段得到3个归并段;外部排序的基本方法第一趟由10个归并段得到5个归并段;假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。分析上述外排过程中访问外存(对外存进行读/写)的次数：1)求得10个初始归并段需访问外存100次;2)每进行一趟归并需访问外存100次;3)总计访

50、问外存 100+4 100=500次外部排序的基本方法外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间tIO值取决于外存，远远大于tIS和tmg。外部排序的时间取决于读写外存的次数d。外部排序总时间=产生初始归并段的时间 m*tIS+外存信息读写时间 d*tIO+内部归并所需时间 s*utmg外部排序的基本方法例如:若对上述例子采用2 路归并,则只需进行4趟归并，外排所需总的时间：10*tIS+500*tIO+4*1000*tmg若对上述例子采用5 路归并,则只需进行2趟归并，总的访问外存的次数为100+2 100=300次一般情况下，假设待排记录序列含 m 个初始归并段，外

51、排时采用 k路归并，则归并趟数s=logkm ，显然，随着k的增大或m的减小，归并的趟数将减少，因此对外排而言，通常采用多路归并。k 的大小可选，但需综合考虑各种因素。外部排序的基本方法分析:m 个初始归并段，外排时采用 k 路归并，则归并趟数为 logkm ,K 大，趟数减少，读写记录的总数将减少。但 K 大，会使内部归并时间tmg增大?。一、多路平衡归并的性质：多路平衡归并的实现 设从 k 个元素中挑选一个最小的元素需(k-1)次比较。每次比较耗费的时间代价为 tmg，在进行 k 路平衡归并时,要得到m个初始归并段,则内部归并过程中进行的比较的总的次数为:logkm (k-1)(n-1)t

52、mg=log2m (k-1)/log2k (n-1)tmg 改进：采用胜者树或者败者树，从 K 个元素中挑选一个最小的元素仅需 log2k 次比较，这时总的时间耗费将下降为：log2m (n-1)tmg 多路平衡归并的实现二、胜者树及其使用195729595765432输入缓冲区7654321559572995164952787122584912938576671922474859输出 缓冲区54路平衡归并多路平衡归并的实现97729169751649527871225849129385766719224748597654321输入缓冲区输出 缓冲区779167299765432157二、胜者

53、树及其使用4路平衡归并多路平衡归并的实现91212291699516495278712258491293857667192247485976543219129161229976543215794路平衡归并二、胜者树及其使用多路平衡归并的实现输入缓冲区输出 缓冲区改进：采用胜者树，从K个元素中选取最小元素之后，从根结点到它的相应的叶子结点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。采用胜者树，从 K 个元素中挑选一个最小的元素仅需 log2m (n-1)tmg即内部归并时间与k无关,K 增大，归并趟数 logkm 减少，读写外存次数减少，外排总时间减少。多路平衡归并的实现21

54、三、败者树及其使用7295935164952787122584912938576671922474859b0ls1输入缓冲区输出 缓冲区97295729976543215注意：挑出冠军需要进行 k-1 次比较，此处需要比较 3 次。0ls 005ls2ls3b1b2b34路平衡归并多路平衡归并的实现20三、败者树及其使用72916935164952787122584912938576671922474859b0ls1输入缓冲区输出 缓冲区 9 7 29 57 299765432157注意：挑出冠军需要进行 k-1 次比较，此处需要比较 3 次。1ls 00 5ls2ls3b1b2b34路平衡归

55、并多路平衡归并的实现20三、败者树及其使用122916915164952787122584912938576671922474859b0ls1输入缓冲区输出 缓冲区9729572997654321579注意：挑出冠军需要进行 k-1 次比较，此处需要比较 3 次。3ls 005ls2ls3b1b2b34路平衡归并多路平衡归并的实现一、问题的提出 m个初始归并段做k路平衡归并排序时归并的趟数为logkm.为了减少归并趟数，也可以减小m的值。如何减小初始归并段的个数（也就是增加归并段的长度）?解决：在内存长度一定时，假设容纳M条记录，按照通常的 排序方法，初始归并段的长度可以是M一种更好的方法是使

56、用置换选择(replace selection)算法，平均情况下可以产生可以生成两倍内存长度的初始归并段。置换-选择排序2.置换选择排序置换选择排序是堆排序的变体。输入文件FI内存工作区WA输出文件Fo内存工作区可容纳w个记录输出缓冲输入缓冲置换-选择排序(1)从FI输入W个记录到WA；(2)从WA中选择关键字最小的记录，记为MINIMAX(3)将MINIMAX输出到FO中；(4)若FI不空，从FI输入下一个记录到WA；(5)从WA中所有关键字比MINIMAX的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。(6)重复（3）-（5）直至WA中选不出新的MINIMAX。到此得到一

57、个初始归并段(7)重复（2）-（6），直至WA为空。置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI51 49 39 46 38 29WAFO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14

58、、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI51 49 39 46 38 14WA29FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择

59、分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI51 49 46 39 14 61WA29 38FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46

60、 58 33 76 FI51 49 46 14 61 15WA29 38 39FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI51 49 14 61 15 30WA29 38 39 46FO置换-选择排序的操作过程实例：输入文件FI中记

61、录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI51 14 61 15 30 1WA29 38 39 46 49FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24

62、、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI14 61 15 30 1 48WA29 38 39 46 49 51#FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 4

63、6 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI14 15 30 1 48 52WA29 38 39 46 49 51 61FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33

64、76 FI14 15 30 1 48 52WA29 38 39 46 49 51 61#FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI14 15 30 48 52 3WA29 38 39 46 49 51 61#1 FO置换-选择排序

65、的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI14 15 30 48 52 63WA29 38 39 46 49 51 61#1 3FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30

66、、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI15 30 48 52 63 27WA29 38 39 46 49 51 61#1 3 14FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI30 48 52 63 27 4WA29 38 39 46 49 51 61#1 3 14 15 FO置换-选择排序的操作过程实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、6