数据结构(C语言版)第8章-排序课件.ppt

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）0 1 2 3 4 5 6i=2i=3i=5i=4i=6252525494949252525*16161608080808初态：完成!将序列存入顺序表L中，将L.r0作为哨兵（21，25，49，25*，16，08

6、）*表示后一个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向前进行顺序查找，监视哨设置在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插入位置直接插入排

7、序关键字大于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.rj.key;-j)L.rj+1=L.rj;/记录后移 L.rj+1=L.r0;/插入到正确位置 算法分析 设对象个数为n，则执行n-1趟 比较次数和移动次数与初始排列有关最好情况下：每趟只需比较

8、 1 次，不移动 总比较次数为 n-1for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)最坏情况下：第 i 趟比较i次，移动i+1次算法分析2)1)(2(2nnini比较次数:2)1)(4()1(2nnini移动次数:if(L.ri.keyL.ri-1.key)L.r0=L.ri;/复制为哨兵 L.ri=L.ri-1;L.rj+1=L.r0;/插入到正确位置 若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况 平均情况比较次数和移动次数为n2/4时间复杂度为 o(n2)空间复杂度为 o(1)是一种稳定的排序方法0 1 2 3 4 5算法分析折

9、半插入排序直接插入排序 减少关键字间的比较次数在插入 ri 时，利用折半查找法寻找 ri 的插入位置算法分析212549251608lowhighi=2折半插入排序212549251608lowhighmi=3折半插入排序212549251608lowhighm212549251608low/mhighi=4折半插入排序212549251608lowhighm212549251608low/mhighi=5折半插入排序212549251608lowhighm212549251608lowhighmi=6折半插入排序2 12 54 92 51 60 8void BInsertSort(SqLis

10、t&L)for(i=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 9797551327044949*

13、3876 65 9713 27 0449*76 97 ri dk 值较大，子序列中对象较少，速度较快；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.len

14、gth；+i)if(ri.key 0&(r0.keyrj.key);j=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

15、概述插入排序交换排序选择排序归并排序基数排序外部排序Contents交换排序基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。起泡排序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

16、main()int a11;/*a0不用，之用a1a10*/int i,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 比较次数和移动次数与初始排列有关只

17、需 1趟排序，比较次数为 n-1，不移动 while(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;最好情况下：算法分析u时间复杂度为 o(n2)(21)(211nninni)(23)(321nninni需 n-1趟排序，第i趟比较n-i次，移动3(n-i)次最坏情况下：u空间复杂度为 o(1)u是一种稳定的排序方法快速排序基本思想：任取一个元素(如第一个)为中心所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个

18、0 1 2 3 4 5pivotkeypivotkeypivotkey快速排序快速排序pivotkey 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界点快

19、速排序快速排序 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 849383865659797767613132

20、7274949highlow49界点快速排序 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 849383865

21、6597977676131327274949highlow49界点快速排序 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

22、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 8493838656597977676131327274949highlow49界点

23、快速排序 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 849383865659797767613132727

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

25、 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.rlow=L.r0;return low;快速排序可以证明，平均计算时间是O(nlog2n)。算法分析实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时参

26、数（新的low和high）。最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n)。2121211nnninni)()(算法分析最坏从小到大排好序，递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列，必须经过 n-1 趟才能把所有对象定位，而且第 i 趟需要经过 n-i 次关键码比较才能找到第 i 个对象的安放位置。最好划分后，左侧右侧子序列的长度相同算法分析时间效率：O(nlog2n)每趟确定的元素呈指数增加123稳 定 性：不稳定 可选任一元素为支点。空间效率：O（log2n）递归要用到栈空间目 录 导 航8.18.28.38.48.58.68.7概述插入

27、排序交换排序选择排序归并排序基数排序外部排序Contents选择排序基本思想：每一趟在后面 n-i+1个中选出关键码最小的对象,作为有序序列的第 i 个记录2125*i=125164908最小者 08交换21,0825160825*4921i=2最小者 16交换25,1649i=3081625*2521最小者 21交换49,21简单选择排序490 1 2 3 4 5i=408162521最小者 25*无交换25*i=549最小者 25无交换2521160825160825*4921结果各趟排序后的结果简单选择排序void SelectSort(SqList&K)for(i=1;iL.lengt

28、h;+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)稳定)(21)(211nninni比较次数：移动次数最好情况：0最坏情况：3(n-1)BAOBAODIAOCHABAODIAOWANGZHAOCHALIUBAODIAOYANGXUEWANG树形选择排序DIAOCHADIAOWANGZHAOCHALIUDIAOYANGXUEWANG树形选择排序CHACHADIAOCHALIUDIAO

29、WANGZHAOCHALIU*DIAOYANGXUEWANG树形选择排序DIAOLIUDIAOWANGZHAOLIU*DIAOYANGXUEWANG树形选择排序BIAOLIUDIAOZHAOLIUDIAOWANGZHAO*LIU*DIAOYANGXUEWANG树形选择排序改进：简单选择排序没有利用上次选择的结果，是造成速度慢的重要原因。如果，能够加以改进，将会提高排序的速度。381376276549974938651327133813选出最小者 13树形选择排序改进：简单选择排序没有利用上次选择的结果，是造成速度满的重要原因。如果，能够加以改进，将会提高排序的速度。38137627654997

30、4938651327133813选出次最小者，应利用上次比较的结果。从被 13 打败的结点 27、76、38 中加以确定。树形选择排序改进：简单选择排序没有利用上次选择的结果，是造成速度满的重要原因。如果，能够加以改进，将会提高排序的速度。381376276549974938651327133813选出次最小者，应利用上次比较的结果。从被 13 打败的结点 27、76、38 中加以确定。树形选择排序n个元素的序列k1,k2,kn，当且仅当满足下列关系时，成为堆：122122iiiiiiiikkkkkkkk或堆排序什么是堆？如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。

31、(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,35,28,50,38,25,47,15)是否为堆807540627328355038254715完全二叉树大根堆堆排序将无序序列建成一个堆输

32、出堆顶的最小（大）值使剩余的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 个元素起，至第一个元素止，进行反复筛选堆堆排序 70 1 60 240 4 30 5 12 3 8 610 7 1 2 3 4 5 6 7 3060 840701210无序序列建

33、成堆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 8610 7 70 60 1 2 3 4 5 6 7 3070124060810无序序列建成堆3 1 70 240 4 60 5 12 3 8 61

34、0 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 3 4 5 6 7 7060124030810堆的重新调整1 1 60 240 4 30 5 12 3 8 610 7 70堆的重新调整1 60

35、40 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 510 17060124030810707010 60106010104040堆的重新调整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 6010 7 1 2 3 4 5 6 7 3 6 28 540 1403012108601070706060堆的重新调整3 3

36、010 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 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新调整4 1030 4

37、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 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 1810830860107070606040403030121

38、2堆的重新调整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 18883086010707060604040303012121010算法分析时间效率：O(nlog2n)空间效率：O（1）稳 定 性：不稳定适用于n 较大的情况目 录 导 航8.18

39、.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 44913659776780AB0 1 2 3 4 5 6 7 Cjk将两个顺序表合并成一个有序表7i0 1 2 3 449136597767

40、80AB0 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 44913659776780AB0 1 2 3 4 5 6 7 Cijk将两个顺序表合并成一个有序表71349650 1 2 3 4

41、4913659776780AB0 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将两个顺序表合并成一个有序表71349657680B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可0 1 2

42、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）稳 定 性：稳定 以扑克牌排序为例。每张扑克牌有两个“排序码”：花色和面值。其有序关系为：u 花色：u 面值：2 3 4 5 6 7 8 9 10 J Q K A 可以把所有扑克

43、牌排成以下次序：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 Significant Digit first)最低位优先LSD(Least Significant Digit first)

44、基数排序链式基数排序：用链表作存储结构的基数排序链式基数排序最高位优先法十进制数比较可以看作是一个多关键字排序先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序，就可以得到一个有序的序列。278,109,063,930,184,589,269,008,083按百位排序008,063,083269,278589930109,184按个位排序008063083109184269278589930最高位优先法十位首先依据最低位排序码Kd对所有对象进行

45、一趟排序。再依据次低位排序码Kd-1对上一趟排序结果排序。依次重复，直到依据排序码K1最后一趟排序完成，就可以得到一个有序的序列。最低位优先法这种方法不需要再分组，而是整个对象组都参加排序278，109，063，930，184，589，269，008，083按个位排序930，063，083，184，278，008，109，589，269按十位排序008，109，930，063，169，278，083，184，589按百位排序008，063，083，109，169，184，278，589，930，最高位优先法 先决条件：链式基数排序利用“分配”和“收集”对关键字进行排序 过程 首先对低位关键字排

46、序，各个记录按照此位关键字的值分配到相应的序列里。按照序列对应的值的大小，从各个序列中将记录收集，收集后的序列按照此位关键字有序。在此基础上，对前一位关键字进行排序。知道各级关键字的主次关系知道各级关键字的取值范围初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：链式基数排序505008109930063269278083184589二趟收集：08318458

47、9063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集链式基数排序008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集链式基数排序设置10个队列，fi和ei分别头指针和尾指针链式基数排序步骤010203040506070

48、8 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列重复执行d趟“分配”与“收集”每趟对 n 个记录进行“分配”，对rd个队列进行“收集”需要增加n+2rd个附加链接指针。n个记录每个记录有 d 位关键字关键字取值范围rd(如十进制为10)算法分析 时间效率：O(空间效率：O(稳 定 性：稳定目 录 导 航8.18.28.38.

49、48.58.68.7概述插入排序交换排序选择排序归并排序基数排序外部排序Contents由相对独立的两个步骤组成：外部排序的基本过程123按可用内存大小,利用内部排序方法，构造若干个记录的有序子序列写入外存，通常称这些记录的有序子序列为“归并段”;通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。例如：假设有一个含10,000个记录的磁盘文件，而当前所用的计算机一次只能对1,000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。假设进行2路归并(即两两归并)：最后一趟归并得到整个记录的有序序列。第三趟由 3 个归并段得

50、到2个归并段;第二趟由 5 个归并段得到3个归并段;外部排序的基本方法第一趟由10个归并段得到5个归并段;假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。分析上述外排过程中访问外存(对外存进行读/写)的次数：1)求得10个初始归并段需访问外存100次;2)每进行一趟归并需访问外存100次;3)总计访问外存 100+4 100=500次外部排序的基本方法外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间tIO值取决于外存，远远大于tIS和tmg。外部排序的时间取决于读写外存的次数d。外部