《第八章-排序要点.ppt》由会员分享，可在线阅读，更多相关《第八章-排序要点.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章第八章 排序排序 内容提要内容提要：u五类内部排序方法（插入排序、交换排序、选择排序、归并排序和基数排序）的基本思想、排序过程、实现的算法、算法的效率分析及排序的特点；u各种排序方法的比较和选择；u最后简单介绍外部排序。排序的功能是将一个数据元素(记录)的任意序列，重新排列成一个按关键字有序的序列。排序的定义2排序的分类l按待排序记录所在位置按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序l按排序依据原则按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序
2、3排序的基本操作l比较两个关键字大小比较两个关键字大小l将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置4定义待排序的记录的数据类型为：typedef struct int key;elemtype data;redtype;redtype rn;排序对象的数据类型5基本思想：每步将一个待排序的记录，按其关键字值的大小插入到前面已经排序的文件中适当的位置上，直到全部插完为止。插入排序基本思路是依次把待排序的记录逐一按其关键字的大小插入到一个已经排好序的有序序列中去，直到所有的记录插完为止。得到一个新的有序序列。插入排序直接插入排序例49 38 65 97 76 13 27i=2
3、 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)排序结果：比较次数 移动次数2 11 02 1.1 06 56 5插入排序直接插入排序8（1）设置监视哨 r0，将待插入记录的值赋给r0;（2）设置开始查找的位置j；（3）在数组
4、中进行搜索，搜索中将第j个记录后移，直至r0.keyrj.key为止（4）将r0插入在rj+1的位置上直接插入排序算法9按平均比较次数计算，将n个记录进行直接插入排序所需的平均比较次数为：直接插入排序算法分析直接插入排序的时间复杂度为O(n2)。空间复杂度为O（1）直接插入排序是一种稳定的排序方法。10插入排序插入排序希尔排序希尔排序希尔排序的作法是：选定第一个增量d1n，把全部记录按此值从第一个记录起进行分组，所有相距为d1的记录作为一组，先在各组内进行插入排序，然后减小间隔，取第二个增量d2r2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为
5、止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。2.对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。3.重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。例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第六趟384976971397279730971376767627301365276530651313
6、49493049273827383038交换排序交换排序冒泡排序冒泡排序17由上述算法可见，当初始序列中记录已按关键字次序排好序，则只需要进行一趟排序，在排序过程中只需要进行n-1次比较，记录移动次数为0；反之，若初始序列中记录按逆序排列，若待排序的序列有n个记录，最多进行n-1趟排序，最大比较次数为交换记录时移动记录的次数也约为3n2/2次，故总的时间复杂度为O(n2)。冒泡排序是稳定的。冒泡排序算法分析冒泡排序算法分析18交换排序交换排序快速排序快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，
7、以达到整个序列有序对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.keyu初始时令i=s,j=tu首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换u再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换u重复上述两步，直至i=j为止u再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止快速排序的排序过程快速排序的排序过程20例初始关键字：49 38 65 97 76 13 27 50 ijxji 完成一趟排序：(27 38 13)49 (76 97 65 50)分别进行快速排序：(13)27 (38)49 (50 65)
8、76 (97)快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序的排序过程快速排序的排序过程211）确定第一个记录为基准记录rt，先从j所指示的位置起向前扫描，当rt.keyrj.key时，交换rt.key和rj.key，使关键字值比基准记录的关键字值小的记录交换到前面；2）从i所指示的位置起向后扫描，直到rt.keyri.key,交换rt.key和ri.key，使关键字值比基准记录的关键字值大的记录交换到后面；3）重复（1）和（2），直至i=j为止完成一趟排序；4）只要tw，重复（1）至（3）分别对基准记录两边的部分进
9、行排序。快速排序的排序算法快速排序的排序算法22快速排序平均时间复杂度为O(nlog2 n)。最坏情况下时间复杂度为O(n2)，快速排序所需的比较次数反而最多。快速排序法不稳定。快速排序需要一个栈空间来实现递归。栈的最大深度为 log2 n 1，所需栈空间为O(log2 n)。最坏情况下，递归深度为n，所需栈空间为O(n)。快速排序的排序算法分析快速排序的排序算法分析23 选择排序选择排序 选择排序是指每次从待排序的记录中选出关键字值最小（或最大）的记录，顺序放在已排序的有序序列中，直到全部排完。选择排序主要包括简单选择排序和堆排序两种。24选择排序选择排序简单选择排序简单选择排序u首先通过n
10、-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换u再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换u重复上述操作，共进行n-1趟排序后，排序结束25例初始：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 76 49 65 四趟：13 27 38 49 76 97 65 五趟：13 27 38 49 65 97 76 六趟：13 27 38 49 65 76
11、97 排序结束：13 27 38 49 65 76 9726(1)查找待排序序列中最小的记录，并将它和该区间第一个记录交换；(2)重复（1）到第n-1次排序后结束简单选择排序算法简单选择排序算法27 简单选择排序所需要的总的比较次数为O(n2)。当初始文件是有序时，最小移动记录次数等于0，而当初始文件是逆序时，每次都要交换记录。直接选择排序是不稳定的.简单选择排序算法分析简单选择排序算法分析28选择排序选择排序堆排序的引入堆排序的引入 堆排序是简单选择排序的改进。用直接选择排序从n个记录中选出关键字值最小的记录要做n-1次比较，然后从其余n-1个记录中选出最小者要作n-2次比较。显然，相邻两趟
12、中某些比较是重复的。为了避免重复比较，可以采用树形选择排序比较。29(a)求出最小关键字3 (b)求出次小关键字11图 8.8 树形选择排序30树形选择排序总的比较次数为O(nlog2 n)，与直接选择排序比较，减少了比较次数，但需要增加额外的存储空间存放中间比较结果和排序结果。选择排序选择排序堆排序的引入堆排序的引入31n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）96279113883132738496
13、5765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值堆的定义堆的定义32 堆排序的基本思路：对一组待排序的记录序列，先将其关键字按堆的定义排列个序列（称初建堆），找到了最小（最大）关键字，将其取出。用剩余的n-1个元素再重建堆，便可得到次小（次大）值。如此反复执行，直到全部关键字排好序为止。堆排序的基本思路33例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 27654950273876
14、9713输出：13 27 38344965502738769713输出：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 65357665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输
15、出：13 27 38 49 50 65 76 9736堆排序的关键问题堆排序需解决的两个问题：堆排序需解决的两个问题：u如何由一个无序序列建成一个堆？u如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？37堆排序的关键问题l第二个问题解决方法第二个问题解决方法筛选筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。l第一个问题解决方法第一个问题解决方法建堆建堆方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端
16、结点）起，至第一个元素止，进行反复筛选。38例：含8个元素的无序序列（49，38，65，97，76，13，27，50），建堆过程：4965382713769750496538271376509749133827657650974913382765765097132738496576509739堆排序只需要一个记录大小的辅助空间。堆排序算法的时间复杂度为O(nlogn)。堆排序是一种不稳定的排序方法。堆排序的算法及分析堆排序的算法及分析40归并排序归并排序 归并排序：把两个或多个有序表进行合并，得到一个新的有序表。将两个有序子文件合并成一个有序文件，称为二路归并。41u设初始序列含有n个记录，则
17、可看成n个有序的子序列，每个子序列长度为1u两两合并，得到n/2个长度为2或1的有序子序列u再两两合并，如此重复，直至得到一个长度为n的有序序列为止 2-路归并排序过程42例初始关键字：49 38 65 97 76 13 27一趟归并后：38 49 65 97 13 76 27二趟归并后：38 49 65 97 13 27 76三趟归并后：132738496576972-路归并排序过程432-路归并排序的关键问题 合并合并是归并排序的核心，即将两个首是归并排序的核心，即将两个首尾相连的有序子表合并成一个有序子尾相连的有序子表合并成一个有序子表。在合并的基础上进行表。在合并的基础上进行一趟排序一
18、趟排序，在一趟排序的基础上完成在一趟排序的基础上完成多趟排序多趟排序。441）设数组r中第一个有序子表从第h 个记录开始至第m个记录为止。即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中。合并的算法合并的算法45 把数组r中的长度为s的相
19、邻有序子表两两合并，归并成一个长度为2s的有序子表，存于t数组中。一趟归并的算法一趟归并的算法46 思路是：第一趟有序子表长s为1，以后每趟s加倍。第一趟将r数组进行归并后存于t数组；第二趟将t数组归并后存于r数组；依次类推，若归并的趟数为奇数，需从t数组复制到r数组。多趟合并的算法多趟合并的算法47归并排序的总的时间复杂度为O(nlog2 n)。归并排序需要的附加存储空间为O(n)，所需辅助空间较大。二路归并排序是稳定的。归并排序算法分析48*基数排序基数排序 基数排序是和前面所述的各种排序方法完全不同的一种排序方法。前面介绍的几种排序方法，都是根据关键字之间的比较和移动记录来实现的，基数排
20、序不需要进行记录关键字间的比较，而是根据组成关键字的各位值，即借助于多关键字排序的思想，用“分配”和“收集”的方法进行排序。49多关键字的排序 l假设有假设有n个记录的序列l R1,R2,，Rnl每个记录每个记录RiRi中含有中含有d d个关键字个关键字(KiKi0 0,Ki,Ki1 1,Ki,Kid-1d-1),),则称上述记录序列则称上述记录序列对关键字(KiKi0 0,KiKi1 1,Ki,Kid-1d-1)有序是指：对于序列中任意是指：对于序列中任意两个记录两个记录RiRi和和Rj(1iRj(1ijnjn)都都满足下列下列(词典)有序关系：关系：l(KiKi0 0,Ki,Ki1 1,K
21、i,Kid-1d-1)(KjKj0 0,Kj,Kj1 1,Kj,Kjd-d-1 1)l其中其中K K0 0被称为被称为“最主最主”位关键字，位关键字，K Kd-1d-1被称被称为为“最次最次”位关键字。位关键字。50实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:l最高位优先MSD法：法：先对K0进行排序，并按，并按K0K0的的不同值将记录序列分成若干子序列之后，分别对不同值将记录序列分成若干子序列之后，分别对K1K1进行排序，进行排序，依次类推，依次类推，直至最后对最次位关键字排序完成为止。l最低位优先LSD法：法：先对Kd-1进行排序，然后对，然后对Kd-2Kd-2进行排序，
22、依次类推，进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据。排序过程中不需要根据“前一前一个个”关键字的排序结果，将记录序列分割成若干关键字的排序结果，将记录序列分割成若干个个(“(“前一个前一个”关键字不同的关键字不同的)子序列。子序列。51例如:学生记录含三个关键字学生记录含三个关键字:系别、班号和班系别、班号和班内的序列号，其中以系别为最主位关键字。内的序列号，其中以系别为最主位关键字。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
23、 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,3052 比较MSD法和LSD法，一般来讲，LSD法要比MSD法来得简单，因为LSD 法是从头到尾进行若干次分配和收集，执行的次数取决于构成关键字值的成分为多少；而MSD 法则要处理各序列与子序列的独立排序问题，就可能复杂一些。MSD法和LSD法的比较53链式基数排序 l假如多关键字的记录序列中，每个关键字的取值假如多关键字的记录序列中，每个关键字的取值范围相同，则按范围相同，则按LSDLSD法进行排序时
24、，可以采用法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键的方法，其好处是不需要进行关键字间的比较。字间的比较。对于数字型或字符型的对于数字型或字符型的单关键字，可以，可以看成是由是由多个数位或多个字符构成的多个数位或多个字符构成的多关键字，此时可以，此时可以采用这种这种“分配-收集”的办法的办法进行排序，称作基数排序法。54链式基数排序 在计算机上实现基数排序时，应采用链表作存在计算机上实现基数排序时，应采用链表作存储结构，即链式基数排序，具体作法为：储结构，即链式基数排序，具体作法为：l待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表；l“分配分配”
25、时，按当前时，按当前“关键字位关键字位”所取值，所取值，将记录分配到不同的将记录分配到不同的“链队列链队列”中，每个队中，每个队列中记录的列中记录的“关键字位关键字位”相同；相同；l“收集收集”时，按当前关键字位取值从小到大时，按当前关键字位取值从小到大将各队列首尾相链成一个链表将各队列首尾相链成一个链表;l对每个关键字位均重复对每个关键字位均重复2)2)和和3)3)两步。两步。55l例如：例如：lp369367167239237138230139l第一次分配得到第一次分配得到lf0230r0lf7367167237r7lf8138r8lf9369239139r9l第一次收集得到第一次收集得到
26、lp230367167237138368239139链式基数排序 56l第二次分配得到第二次分配得到lf3230237138239139r3lf6367167368r6l第二次收集得到第二次收集得到lp230237138239139367167368l第三次分配得到第三次分配得到lf1138139167r1lf2230237239r2lf3367368r3l第三次收集之后便得到记录的有序序列第三次收集之后便得到记录的有序序列lp13813916723023723936736857链式基数排序算法对数据进行d趟扫描，每趟需时间O(n+j)。因此总的计算时间为O(d(n+j)。对于不同的基数j所用
27、的时间是不同的。当n较大或d较小时，这种方法较为节省时间。基数排序适用于链式存储结构的记录的排序，它要求的附加存储量是j个队列的头、尾指针。所以，需要O(n+j)辅助空间。基数排序是一种稳定的排序方法。链式基数排序分析 58各种内部排序方法性能比较方法方法 平均时间平均时间 最坏情况最坏情况 辅助存储辅助存储 简单排序简单排序 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+
28、j)591）从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。2）从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法，都包含在上图中的“简单排序”中。对于希尔排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。3）从稳定性看：直接插入排序、冒泡排序和归并排序是稳定的；而希尔排序、直接选择排序、快速排序和堆排序是不稳定排序。4）从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。各种内部排序方法性能比较60（1）当待排序记录数n 较大时，若要求排序稳定，则采用归并排序。（2）当待排序记录
29、数n 较大，关键字分布随机，而且不要求稳定时，可采用快速排序；（3）当待排序记录数n 较大，关键字会出现正、逆序情形，可采用堆排序（或归并排序）。（4）当待排序记录数n 较小，记录已接近有序或随机分布时，又要求排序稳定，可采用直接插入排序。（5）当待排序记录数n 较小，且对稳定性不作要求时，可采用直接选择排序。选择排序的方法61*外部排序简介外部排序简介在实际问题中，经常会遇到输入文件中记录的数量很大，计算机的内存不能容纳时，排序过程必须借助外部存储器才能完成，这时的排序就称为外部排序。62外存信息的存取外存信息的存取磁带磁带磁带是涂上一层磁性材料的窄带，磁带卷在带盘上，带盘安装在磁带驱动器的
30、转轴上。驱动器控制磁带盘转动，带动磁带移动，通过读/写磁头进行读/写信息的操作。63磁盘存取信息时，首先要确定信息所在的柱面，再将磁头移动到所需磁道的位置上，移动磁头所需的时间称为磁头定位时间或称为寻道时间。然后等待磁道上的信息所在位置随着磁盘的转动而转到磁头下面，这段时间称为等待时间。由于磁盘高速运转（24003600转/分），所以，等待时间是极短的。磁盘的存取时间主要花在磁头定位时间上。外存信息的存取外存信息的存取磁盘磁盘64外部排序的基本方法外部排序的基本方法 最常用的外部排序方法是归并排序法。这种方法由两个阶段组成：第一阶段是把磁盘文件逐段读入到内存，用较好的内部排序方法对这段文件进行
31、排序。已排序的文件段通常称为归并段，且记作R。整个文件经过逐段排序后又逐段写回到外存上。这样，在外存上就形成了许多初始归并段。第二阶段是对这些初始归并段使用某种归并方法（如路归并法），进行多遍归并，使归并段的长度有小变大。最后在外存上形成一个有序的文件。65 一般可依据所使用的外存设备将外部排序分为磁盘文件排序和磁带文件排序。磁盘排序和磁带排序基本相似，区别在于初始归并段在外存储介质中的分布方式不同。磁盘是直接存取设备，而磁带是顺序存储设备，读取信息块的时间与所读信息块的位置关系极大。故在磁带上进行文件排序时，研究归并段信息块的分布是个极为重要的问题。外部排序的基本方法外部排序的基本方法66最
32、简单的归并排序方法与内排序中的二路归并类似。假设一具有n个记录的文件，先把该文件看作是由n个长度为1的顺串组成，然后在此基础上进行两两归并。经过log2n趟归并后，当文件中只含有一个长度为n的顺串时，整个文件的排序就完成了。在每一躺排序过程中都需要进行记录的内、外存交换。外部排序的基本方法外部排序的基本方法67还有一种常用的外部排序方法是多路归并排序。由于在外部排序过程中，数据的内外存交换所需的时间比记录的内部归并所需的时间大得多，所以可以通过减少数据内外存交换的次数来提高外部排序的效率。为了不增加内部归并时所需进行关键字比较的次数，在具体实现时通常不用选择排序的方法，而用“败者树”来实现。外部排序的基本方法外部排序的基本方法68第八章第八章 排序排序 内容提要内容提要：u五类内部排序方法（插入排序、交换排序、选择排序、归并排序和基数排序）的基本思想、排序过程、实现的算法、算法的效率分析及排序的特点；u各种排序方法的比较和选择；u最后简单介绍外部排序。本章要点本章要点 排序的概念和有关知识；插入排序、交换排序、选择排序、归并排序和基数排序五类内部排序方法的基本思想、排序过程、实现的算法、算法的效率分析及排序的特点。各种内部排序方法的优缺点及不同的应用场合选择合适的方法进行排序。