数据结构与程序设计第九章排序.优秀PPT.ppt

《数据结构与程序设计第九章排序.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计第九章排序.优秀PPT.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章第九章 排序排序 内容提要内容提要：五类内部排序方法（插入排序、交换排序、五类内部排序方法（插入排序、交换排序、选择排序、归并排序和基数排序）的基本思选择排序、归并排序和基数排序）的基本思想、排序过程、实现的算法、算法的效率分想、排序过程、实现的算法、算法的效率分析及排序的特点；析及排序的特点；各种排序方法的比较和选择；各种排序方法的比较和选择；最终简洁介绍外部排序。最终简洁介绍外部排序。1排序的功能是将一个数据元素(记录)的随意序列，重新排列成一个按关键字有序的序列，目的是为了便于查询和处理数据。排序的定义2排序的分类l按待排序记录所在位置按待排序记录所在位置l内部排序：待排序记录存放

2、在内存内部排序：待排序记录存放在内存l外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序l按排序依据原则按排序依据原则l插入排序：干脆插入排序、折半插入排序、希尔插入排序：干脆插入排序、折半插入排序、希尔排序排序l交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序l选择排序：简洁选择排序、堆排序选择排序：简洁选择排序、堆排序l归并排序：归并排序：2-2-路归并排序路归并排序3排序的基本操作l比较两个关键字大小比较两个关键字大小l将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置4排序的性质排序的性质 假如在待排序的数据中，存在多个假如在待排

3、序的数据中，存在多个关键字相同的数据，经排序后这些数据关键字相同的数据，经排序后这些数据的相对次序仍旧保持不变，则称相应的的相对次序仍旧保持不变，则称相应的排序方法为稳定方法，否则为不稳定方排序方法为稳定方法，否则为不稳定方法。法。5定义待排序的记录的数据类型为：#define recnum 100 struct rectype int key;int item;struct rectype arecnum+1;排序对象的数据类型6基本思想：每步将一个待排序的记录，按其关键字值的大小插入到前面已经排序的文件中适当的位置上，直到全部插完为止。插入排序7基本思路是依次把待排序的记录逐一按其关键字的

4、大小插入到一个已经排好序的有序序列中去，直到全部的记录插完为止。得到一个新的有序序列。插入排序干脆插入排序8例49 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：比较次数 移

5、动次数1 11 02 1.1 05 56 5插入排序干脆插入排序9（1）设置监视哨 a0，将待插入记录的值赋给a0;（2）设置起先查找的位置j；（3）在数组中进行搜寻，搜寻中将第j个记录后移，直至a0.keyaj.key为止（4）将a0插入在aj+1的位置上干脆插入排序算法10void straipass(a,i)struct rectype arecnum+1;int i;int j,x;a0=ai;j=i-1;x=ai.key;11while(xaj.key)aj+1=aj;j=j-1;aj+1=a0;12void straisort(a,j)struct rectype arecnum+

6、1;int j;int i;for(i=2;i=j;i+)straipass(a,i);13按平均比较次数计算，将n个记录进行干脆插入排序所需的平均比较次数为：干脆插入排序算法分析干脆插入排序的时间困难度为O(n2)。空间困难度为O（1）干脆插入排序是一种稳定的排序方法。14折半插入排序折半插入排序 在进行插入排序时，用折半查找在进行插入排序时，用折半查找法找寻插入位置，从而削减排序过程法找寻插入位置，从而削减排序过程中的比较后移动次数，这就是折半插中的比较后移动次数，这就是折半插入排序。入排序。15折半插入排序的过程折半插入排序的过程l初始化初始化l a0=ail 置折半查找的上下界：置折半

7、查找的上下界：s=1;j=i-1;l当当s=j时重复以下操作：时重复以下操作：l m=(s+j)/2;l 假如假如a0am，则，则j=m-1，否则，否则s=m+116l将插入位置以后的元素向后移一个位将插入位置以后的元素向后移一个位置置l将将a0插入插入as17void binpass(a,i)struct rectype arecnum+1;int i;int x,s,j,m,k;a0=ai;x=ai.key;s=1;j=i-1;18 while(s=j)m=(int)(s+j)/2);if(x=j+1;k-)ak+1=ak;Aj+1=a0;19void binsort(a,j)struct

8、 rectype arecnum+1;int j;int i;for(i=2;i=j;i+)binpass(a,i);20 折半插入排序的时间困难度是折半插入排序的时间困难度是 O（log2n）这种排序方法也是稳定的。这种排序方法也是稳定的。21 基本思想：把记录按下标的确定基本思想：把记录按下标的确定增量分组，对每组记录运用干脆插入增量分组，对每组记录运用干脆插入排序。随着增量渐渐缩小，所分成的排序。随着增量渐渐缩小，所分成的组所包含的记录越来越多，到增量的组所包含的记录越来越多，到增量的值等于值等于1时，全部记录成为一组，且记时，全部记录成为一组，且记录已经相对有序，再进行干脆插入排录已经

9、相对有序，再进行干脆插入排序，即可以完成对全部记录的较高效序，即可以完成对全部记录的较高效率的排序了。率的排序了。插入排序插入排序希尔排序希尔排序22希尔排序的作法是：选定第一个增量d1n，把全部记录按此值从第一个记录起进行分组，全部相距为d1的记录作为一组，先在各组内进行插入排序，然后减小间隔，取其次个增量d2=0&xr2.key，则交换；然后比较其次个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最终一个记录上。312、对前n-1个记录进行其次趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。3、重复上述过程，直到

10、“在一趟排序过程中没有进行过交换记录的操作”为止。32例49 38 65 97 76 13 27 30初始关键字38 49 65 76 13 27 30 97第一趟38 49 65 13 27 30 76第二趟38 49 13 27 30 65第三趟38 13 27 30 49第四趟13 27 30 38第五趟13 27 30第六趟38497697139727973097137676762730136527653065131349493049273827383038交换排序交换排序冒泡排序冒泡排序33for(i=1;i=i1-1;i+)for(j=1;jaj+1.key)temp=aj;aj=

11、aj+1;aj+1=temp;34改进算法改进算法mark=i;while(mark)m=mark-1;mark=0;for(j=1;jaj+1.key)temp=aj;aj=aj+1;aj+1=temp;mark=j;35由上述算法可见，当时始序列中记录已按关键字次序排好序，则只须要进行一趟排序，在排序过程中只须要进行n-1次比较，记录移动次数为0；反之，若初始序列中记录按逆序排列，若待排序的序列有n个记录，最多进行n-1趟排序，最大比较次数为冒泡排序算法分析冒泡排序算法分析36 冒泡排序交换记录时移动记录的次数也约为3n2/2次，故总的时间困难度为O(n2)。冒泡排序是稳定的。37交换排序

12、交换排序快速排序快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序38对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜寻第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜寻，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止快速排序的排序过程快速排序的排序过程39例初始关键字：49 38 65 97 76

13、13 27 50 ijxji 完成一趟排序：(27 38 13)49 (76 97 65 50)分别进行快速排序：(13)27 (38)49 (50 65)76 (97)快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序的排序过程快速排序的排序过程401）确定第一个记录为基准记录rt，先从j所指示的位置起向前扫描，当rt.keyrj.key时，交换rt.key和rj.key，使关键字值比基准记录的关键字值小的记录交换到前面；2）从i所指示的位置起向后扫描，直到rt.keyri.key,交换rt.key和ri.key，使关

14、键字值比基准记录的关键字值大的记录交换到后面；3）重复（1）和（2），直至i=j为止完成一趟排序；4）只要tw，重复（1）至（3）分别对基准记录两边的部分进行排序。快速排序的排序算法快速排序的排序算法41快速排序平均时间困难度为O(nlog2 n)。最坏状况下时间困难度为O(n2)，快速排序所需的比较次数反而最多。快速排序法不稳定。快速排序须要一个栈空间来实现递归。栈的最大深度为 log2 n 1，所需栈空间为O(log2 n)。最坏状况下，递归深度为n，所需栈空间为O(n)。快速排序的排序算法分析快速排序的排序算法分析42 选择排序选择排序 选择排序是指每次从待排序的记录中选出关键字值最小（

15、或最大）的记录，依次放在已排序的有序序列中，直到全部排完。选择排序主要包括简洁选择排序和堆排序两种。43选择排序选择排序简洁选择排序简洁选择排序u首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换u再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与其次个记录交换u重复上述操作，共进行n-1趟排序后，排序结束44例初始：49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：13 27 65 97 76 49 38 三趟：13 27 38 97

16、76 49 65 四趟：13 27 38 49 76 97 65 五趟：13 27 38 49 65 97 76 六趟：13 27 38 49 65 76 97 排序结束：13 27 38 49 65 76 9745(1)查找待排序序列中最小的记录，并将它和该区间第一个记录交换；(2)重复（1）到第n-1次排序后结束简洁选择排序算法简洁选择排序算法46 简洁选择排序所须要的总的比较次数为O(n2)。当时始文件是有序时，最小移动记录次数等于0，而当时始文件是逆序时，每次都要交换记录。干脆选择排序是不稳定的.简洁选择排序算法分析简洁选择排序算法分析47选择排序选择排序堆排序的引入堆排序的引入 堆排

17、序是简洁选择排序的改进。用干脆选择排序从n个记录中选出关键字值最小的记录要做n-1次比较，然后从其余n-1个记录中选出最小者要作n-2次比较。明显，相邻两趟中某些比较是重复的。为了避开重复比较，可以接受树形选择排序比较。48(a)求出最小关键字3 (b)求出次小关键字11图 8.8 树形选择排序49树形选择排序总的比较次数为O(nlog2 n)，与干脆选择排序比较，削减了比较次数，但须要增加额外的存储空间存放中间比较结果和排序结果。选择排序选择排序堆排序的引入堆排序的引入50n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1k

18、ik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值堆的定义堆的定义51 堆排序的基本思路：对一组待排序的记录序列，先将其关键字按堆的定义排列个序列（称初建堆），找到了最小（最大）关键字，将其取出。用剩余的n-1个元素再重建堆，便可得到次小（次大）值。如此反复执行，直到全部关键字排好序为止。堆排序的基本思路52例13273849657650979727384965765013输出：13274

19、9389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 38534965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 655476659727384950

20、13输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 9755堆排序的关键问题堆排序需解决的两个问题：堆排序需解决的两个问题：u如何由一个无序序列建成一个堆？u如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？56堆排序的关键问题l其次个问题解决方法其次个问题解决方法筛选筛选l方法：输出堆顶元素之后，以堆中最终一个元方法：输出堆顶元素之后，以堆中最终一个元素替代之；然后将根结点值与左、右子树的根素替代之；然后将根结点值与左、右子树的根结点值

21、进行比较，并与其中小者进行交换；重结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为称这个从堆顶至叶子的调整过程为“筛选筛选”。l第一个问题解决方法第一个问题解决方法建堆建堆l方法：从无序序列的第方法：从无序序列的第 n/2 个元素（即此无序个元素（即此无序序列对应的完全二叉树的最终一个非终端结点）序列对应的完全二叉树的最终一个非终端结点）起，至第一个元素止，进行反复筛选。起，至第一个元素止，进行反复筛选。57例：含8个元素的无序序列（49，38，65，97，76，13，27，50），建堆过程：

22、4965382713769750496538271376509749133827657650974913382765765097132738496576509758堆排序只须要一个记录大小的协助空间。堆排序算法的时间困难度为O(nlogn)。堆排序是一种不稳定的排序方法。堆排序的算法及分析堆排序的算法及分析59归并排序归并排序 归并排序：把两个或多个有序表进行合并，得到一个新的有序表。将两个有序子文件合并成一个有序文件，称为二路归并。60u设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1u两两合并，得到n/2个长度为2或1的有序子序列u再两两合并，如此重复，直至得到一个长度

23、为n的有序序列为止 2-路归并排序过程61例初始关键字：49 38 65 97 76 13 27一趟归并后：38 49 65 97 13 76 27二趟归并后：38 49 65 97 13 27 76三趟归并后：132738496576972-路归并排序过程622-路归并排序的关键问题 合并合并是归并排序的核心，即将两个首是归并排序的核心，即将两个首尾相连的有序子表合并成一个有序子尾相连的有序子表合并成一个有序子表。在合并的基础上进行表。在合并的基础上进行一趟排序一趟排序，在一趟排序的基础上完成在一趟排序的基础上完成多趟排序多趟排序。631）设数组r中第一个有序子表从第h 个记录起先至第m个记

24、录为止。即rh到rm，其次个有序子表从第m+1个记录起先到第w个记录为止，即rm+1到rw，最终形成的有序表为rh到rw；2）设置I,j,k分别指向（1）中所指的三个有序表的第一个单元。3）比较ri和rj的关键字值的大小，若ri.keyrj.key，则将第一个有序子表的记录ri复制到数组ak中，并使i+,k+;4）否则，将其次个有序子表的记录rj复制到ak中，并使j+,k+。依次类推，直到全部记录复制到rh到rw中。合并的算法合并的算法64 把数组r中的长度为s的相邻有序子表两两合并，归并成一个长度为2s的有序子表，存于t数组中。一趟归并的算法一趟归并的算法65 思路是：第一趟有序子表长s为1

25、，以后每趟s加倍。第一趟将r数组进行归并后存于t数组；其次趟将t数组归并后存于r数组；依次类推，若归并的趟数为奇数，需从t数组复制到r数组。多趟合并的算法多趟合并的算法66归并排序的总的时间困难度为O(nlog2 n)。归并排序须要的附加存储空间为O(n)，所需协助空间较大。二路归并排序是稳定的。归并排序算法分析67*基数排序基数排序 基数排序是和前面所述的各种排序方法完全不同的一种排序方法。前面介绍的几种排序方法，都是依据关键字之间的比较和移动记录来实现的，基数排序不须要进行记录关键字间的比较，而是依据组成关键字的各位值，即借助于多关键字排序的思想，用“安排”和“收集”的方法进行排序。68多

26、关键字的排序 l假设有假设有n n个记录的序列个记录的序列l R1,R2,R1,R2,，RnRnl每个记录每个记录RiRi中含有中含有d d个关键字个关键字(Ki0,Ki1,(Ki0,Ki1,Kid-1),Kid-1),则称上述记录序列对关键字则称上述记录序列对关键字(Ki0,Ki1,Kid-1)(Ki0,Ki1,Kid-1)有序是指：对于序有序是指：对于序列中随意两个记录列中随意两个记录RiRi和和Rj(1ijn)Rj(1ijn)都满都满足下列足下列(词典词典)有序关系：有序关系：l(Ki0,Ki1,Kid-1)(Kj0,Kj1,(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1),

27、Kjd-1)l其中其中K0K0被称为被称为“最主最主”位关键字，位关键字，Kd-1Kd-1被被称为称为“最次最次”位关键字。位关键字。69实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:l最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，依次类推，直至最终对最次位关键字排序完成为止。l最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不须要依据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。70例如:学生记录含三个关键字

28、学生记录含三个关键字:系别、班号和班系别、班号和班内的序列号，其中以系别为最主位关键字。内的序列号，其中以系别为最主位关键字。LSD的排序过程如下的排序过程如下:无序序列无序序列3,2,30 1,2,15 3,1,20 2,3,18 2,1,20对对K2排序排序1,2,15 2,3,18 3,1,20 2,1,20 3,2,30对对K1排序排序3,1,20 2,1,20 1,2,15 3,2,30 2,3,18对对K0排序排序1,2,15 2,1,20 2,3,18 3,1,20 3,2,3071 比较MSD法和LSD法，一般来讲，LSD法要比MSD法来得简洁，因为LSD 法是从头到尾进行若干

29、次安排和收集，执行的次数取决于构成关键字值的成分为多少；而MSD 法则要处理各序列与子序列的独立排序问题，就可能困难一些。MSD法和LSD法的比较72链式基数排序 l假如多关键字的记录序列中，每个关键字的取值假如多关键字的记录序列中，每个关键字的取值范围相同，则按范围相同，则按LSDLSD法进行排序时，可以接受法进行排序时，可以接受“安排安排-收集收集”的方法，其好处是不须要进行关键的方法，其好处是不须要进行关键字间的比较。字间的比较。l 对于数字型或字符型的单关键字，可以看成是对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可由多个数位或多个字符构成的多关键字

30、，此时可以接受这种以接受这种“安排安排-收集收集”的方法进行排序，称的方法进行排序，称作基数排序法。作基数排序法。73链式基数排序 在计算机上实现基数排序时，应接受链表作存在计算机上实现基数排序时，应接受链表作存储结构，即链式基数排序，具体作法为：储结构，即链式基数排序，具体作法为：待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表；“安排安排”时，按当前时，按当前“关键字位关键字位”所取值，将所取值，将记录安排到不同的记录安排到不同的“链队列链队列”中，每个队列中，每个队列中记录的中记录的“关键字位关键字位”相同；相同；“收集收集”时，按当前关键字位取值从小到大将时，按当

31、前关键字位取值从小到大将各队列首尾相链成一个链表各队列首尾相链成一个链表;对每个关键字位均重复对每个关键字位均重复2)2)和和3)3)两步。两步。74l例如：例如：lp369367167239237138230139l第一次安排得到第一次安排得到lf0230r0lf7367167237r7lf8138r8lf9369239139r9l第一次收集得到第一次收集得到lp230367167237138368239139链式基数排序 75l其次次安排得到其次次安排得到lf3230237138239139r3lf6367167368r6l其次次收集得到其次次收集得到lp23023713823913936

32、7167368l第三次安排得到第三次安排得到lf1138139167r1lf2230237239r2lf3367368r3l第三次收集之后便得到记录的有序序列第三次收集之后便得到记录的有序序列lp13813916723023723936736876链式基数排序算法对数据进行d趟扫描，每趟需时间O(n+j)。因此总的计算时间为O(d(n+j)。对于不同的基数j所用的时间是不同的。当n较大或d较小时，这种方法较为节约时间。基数排序适用于链式存储结构的记录的排序，它要求的附加存储量是j个队列的头、尾指针。所以，须要O(n+j)协助空间。基数排序是一种稳定的排序方法。链式基数排序分析 77各种内部排序

33、方法性能比较方法方法 平均时间平均时间 最坏情况最坏情况 辅助存储辅助存储 简单排序简单排序 O(n2)O(n2)O(1)快速排序快速排序 O(nlog2n)O(n2)O(nlog2n)堆排序堆排序 O(nlog2n)O(nlog2n)O(1)归并排序归并排序 O(nlog2n)O(nlog2n)O(n)基数排序基数排序 O(d(n+j)O(d(n+j)O(n+j)781）从平均时间而言：快速排序最佳。但在最坏状况下时间性能不如堆排序和归并排序。2）从算法简洁性看：由于干脆选择排序、干脆插入排序和冒泡排序的算法比较简洁，将其认为是简洁算法，都包含在上图中的“简洁排序”中。对于希尔排序、堆排序、

34、快速排序和归并排序算法，其算法比较困难，认为是困难排序。3）从稳定性看：干脆插入排序、冒泡排序和归并排序是稳定的；而希尔排序、干脆选择排序、快速排序和堆排序是不稳定排序。4）从待排序的记录数n的大小看，n较小时，宜接受简洁排序；而n较大时宜接受改进排序。各种内部排序方法性能比较79（1）当待排序记录数n 较大时，若要求排序稳定，则接受归并排序。（2）当待排序记录数n 较大，关键字分布随机，而且不要求稳定时，可接受快速排序；（3）当待排序记录数n 较大，关键字会出现正、逆序情形，可接受堆排序（或归并排序）。（4）当待排序记录数n 较小，记录已接近有序或随机分布时，又要求排序稳定，可接受干脆插入排

35、序。（5）当待排序记录数n 较小，且对稳定性不作要求时，可接受干脆选择排序。选择排序的方法80*外部排序简介外部排序简介在实际问题中，常常会遇到输入文件中记录的数量很大，计算机的内存不能容纳时，排序过程必需借助外部存储器才能完成，这时的排序就称为外部排序。81外存信息的存取外存信息的存取磁带磁带磁带是涂上一层磁性材料的窄带，磁带卷在带盘上，带盘安装在磁带驱动器的转轴上。驱动器限制磁带盘转动，带动磁带移动，通过读/写磁头进行读/写信息的操作。82磁盘存取信息时，首先要确定信息所在的柱面，再将磁头移动到所需磁道的位置上，移动磁头所需的时间称为磁头定位时间或称为寻道时间。然后等待磁道上的信息所在位置

36、随着磁盘的转动而转到磁头下面，这段时间称为等待时间。由于磁盘高速运转（24003600转/分），所以，等待时间是极短的。磁盘的存取时间主要花在磁头定位时间上。外存信息的存取外存信息的存取磁盘磁盘83外部排序的基本方法外部排序的基本方法 最常用的外部排序方法是归并排序法。这种方法由两个阶段组成：第一阶段是把磁盘文件逐段读入到内存，用较好的内部排序方法对这段文件进行排序。已排序的文件段通常称为归并段，且记作R。整个文件经过逐段排序后又逐段写回到外存上。这样，在外存上就形成了很多初始归并段。其次阶段是对这些初始归并段运用某种归并方法（如路归并法），进行多遍归并，使归并段的长度有小变大。最终在外存上形

37、成一个有序的文件。84 一般可依据所运用的外存设备将外部排序分为磁盘文件排序和磁带文件排序。磁盘排序和磁带排序基本相像，区分在于初始归并段在外存储介质中的分布方式不同。磁盘是干脆存取设备，而磁带是依次存储设备，读取信息块的时间与所读信息块的位置关系极大。故在磁带上进行文件排序时，探讨归并段信息块的分布是个极为重要的问题。外部排序的基本方法外部排序的基本方法85最简洁的归并排序方法与内排序中的二路归并类似。假设一具有n个记录的文件，先把该文件看作是由n个长度为1的顺串组成，然后在此基础上进行两两归并。经过log2n趟归并后，当文件中只含有一个长度为n的顺串时，整个文件的排序就完成了。在每一躺排序

38、过程中都须要进行记录的内、外存交换。外部排序的基本方法外部排序的基本方法86还有一种常用的外部排序方法是多路归并排序。由于在外部排序过程中，数据的内外存交换所需的时间比记录的内部归并所需的时间大得多，所以可以通过削减数据内外存交换的次数来提高外部排序的效率。为了不增加内部归并时所需进行关键字比较的次数，在具体实现时通常不用选择排序的方法，而用“败者树”来实现。外部排序的基本方法外部排序的基本方法87第八章第八章 排序排序 内容提要内容提要：五类内部排序方法（插入排序、交换排序、五类内部排序方法（插入排序、交换排序、选择排序、归并排序和基数排序）的基本思选择排序、归并排序和基数排序）的基本思想、排序过程、实现的算法、算法的效率分想、排序过程、实现的算法、算法的效率分析及排序的特点；析及排序的特点；各种排序方法的比较和选择；各种排序方法的比较和选择；最终简洁介绍外部排序。最终简洁介绍外部排序。88本章要点本章要点 排序的概念和有关学问；插入排序、交换排序、选择排序、归并排序和基数排序五类内部排序方法的基本思想、排序过程、实现的算法、算法的效率分析及排序的特点。各种内部排序方法的优缺点及不同的应用场合选择合适的方法进行排序。89