第9章--排序总结优秀PPT.ppt

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

1、liruinwnu.edu 1第第9 9章章 排序排序9.1 9.1 插入排序插入排序9.2 9.2 交换排序交换排序9.3 9.3 选择排序选择排序9.4 9.4 归并排序归并排序9.5 9.5 基数排序基数排序9.6 9.6 各种内部排序方法的比较探讨各种内部排序方法的比较探讨29.1 9.1 插入排序插入排序一、干脆插入排序一、干脆插入排序二、折半插入排序二、折半插入排序三、希尔排序三、希尔排序3一、干脆插入排序一、干脆插入排序 l干脆插入排序的基本操作是将一个记录干脆插入排序的基本操作是将一个记录插入到已排好的有序表中，从而得到一插入到已排好的有序表中，从而得到一个新的、记录数增加个新

2、的、记录数增加1 1的有序表。的有序表。l例如：已知待排序的一组记录的初始排例如：已知待排序的一组记录的初始排列如下所示：列如下所示：R（49），），R（38），），R（65），），R（97），），R（76），），R（13），），R（27），），R（19）。）。4l假设在排序过程中，前四个记录已按关键字递增的次序，重假设在排序过程中，前四个记录已按关键字递增的次序，重新排列，构成一个含新排列，构成一个含4个记录的有序序列个记录的有序序列:l现要将第现要将第5个（关键字为个（关键字为76）的记录插入上述序列，可以得到）的记录插入上述序列，可以得到一个新的含一个新的含5个记录的有序序列，个记录的有

3、序序列，则首先要找到插入的位置，则首先要找到插入的位置，然后进行插入。然后进行插入。l假设从假设从R（97）起向左进行依次查找，由于）起向左进行依次查找，由于65 76 97，则则R（76）应插入在）应插入在R（65）和）和R（97）之间，从而得到下列）之间，从而得到下列新的有序序列新的有序序列:lR（38），），R（49），），R（65），），R（76），），R（97）（2）l称从式（称从式（1）到式（）到式（2）的过程为一趟干脆插入排序。）的过程为一趟干脆插入排序。l38，49，65，97 （1）5l一般状况下，第一般状况下，第i i趟干脆插入排序的操作为：趟干脆插入排序的操作为：l在含有

4、在含有i-1i-1个记录的有序子序列个记录的有序子序列r1r1i-1i-1中插入一个记中插入一个记录录riri后，变成含有后，变成含有i i个记录的有序子序列个记录的有序子序列r1r1ii；l并且，和依次查找类似，为了在查找插入位置的过并且，和依次查找类似，为了在查找插入位置的过程中避开数组下标出界，在程中避开数组下标出界，在r0r0处设置监视哨。处设置监视哨。l整个排序过程为进行整个排序过程为进行n-1n-1趟插入，即：先将序列中的第趟插入，即：先将序列中的第一个记录看成是一个有序序列的子序，然后从第一个记录看成是一个有序序列的子序，然后从第2 2个记个记录起逐个进行插入直至整个序列变成按关

5、键字非递减有录起逐个进行插入直至整个序列变成按关键字非递减有序序列为止。序序列为止。l在自在自i-1i-1起往前搜寻的过程中，可以同时后移记录。起往前搜寻的过程中，可以同时后移记录。6例例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)2727jjjjjj9776654

6、93827 排序结果：排序结果：(13 27 38 49 65 76 (13 27 38 49 65 76 97)97)7l记录按关键字非递增有序排列时比较的次记录按关键字非递增有序排列时比较的次数达最大值数达最大值记录移动次数达到最大值记录移动次数达到最大值l关键字间的比较次数和移动记录的次数关键字间的比较次数和移动记录的次数,约为约为n2/4n2/4。由此，干脆插入排序的时间。由此，干脆插入排序的时间困难度为困难度为OO（n2 n2）。）。l记录按关键字非递减有序排列时比较的记录按关键字非递减有序排列时比较的次数达最小值次数达最小值:记录不需要移动。记录不需要移动。8二、折半插入排序二、折

7、半插入排序l插入排序的基本操作是在一个有序表中进插入排序的基本操作是在一个有序表中进行查找和插入，则从上章的探讨可知，这行查找和插入，则从上章的探讨可知，这个个“查找查找”操作可利用操作可利用“折半查找折半查找”来实来实现，由此进行的插入排序称之为折半插入现，由此进行的插入排序称之为折半插入排序。排序。9i=1 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20.i=8 20 (6 13 20 30 39 42 70 85)折半插入排序折半插入排序i=8 20 (6 13 30 39 42 70 85)20lowhighmidi=8 20

8、 (6 13 30 39 42 70 85)20lowhighmidi=8 20 (6 13 30 39 42 70 85)20low highmidi=8 20 (6 13 30 39 42 70 85)20lowhigh10三、希尔排序三、希尔排序l基本思想：先将整个待排记录序列分割成基本思想：先将整个待排记录序列分割成若干子序列分别进行干脆插入排序，待整若干子序列分别进行干脆插入排序，待整个序列中的记录个序列中的记录“基本有序基本有序”时，再对全时，再对全体记录进行一次干脆插入排序。体记录进行一次干脆插入排序。l排序过程：先取一个正整数排序过程：先取一个正整数d1nd1n，把全部，把全部

9、记录分成若干个组，全部距离为记录分成若干个组，全部距离为d1d1倍数的倍数的记录放一组，在各组内进行插入排序记录放一组，在各组内进行插入排序;然后然后取取d2d1d2d1，重复上述分组和排序工作，重复上述分组和排序工作;直至直至di=1di=1，即全部记录放进一个组中排序为止，即全部记录放进一个组中排序为止11例：例：49 38 65 97 76 13 27 48 55 4一趟排序：一趟排序：13 27 48 55 4 49 38 65 97 76取取d d1 1=5=5一趟分组一趟分组：49 38 65 97 76 13 27 48 55 449 38 65 97 76 13 27 48 5

10、5 4ji49133827jiji6548ji9755ji76412二趟排序：二趟排序：13 4 48 38 27 49 55 65 97 76取取d2=3二趟分组：二趟分组：13 27 48 55 4 49 38 65 97 7613 27 48 55 4 49 38 65 97 76jiji274jiji5538jijiji13取取d3=1三趟分组：三趟分组：13 4 48 38 27 49 55 65 97 76三趟排序：三趟排序：4 13 27 38 48 49 55 65 76 97l希尔排序所需的比较和移动次数约为希尔排序所需的比较和移动次数约为n1.3n1.3，当，当n n 时，

11、可削减到时，可削减到n(log2n)2n(log2n)2。149.2 9.2 交换排序交换排序一、起泡排序一、起泡排序二、快速排序二、快速排序15一、起泡排序一、起泡排序p首先将最终一个记录的关键字与倒数其次首先将最终一个记录的关键字与倒数其次个记录的关键字进行比较，若为逆序个记录的关键字进行比较，若为逆序rn.keyrn-1.keyrn.keyrn-1.key，则将两个记录交换；，则将两个记录交换；然后依次类推，直至第然后依次类推，直至第2 2个记录和第个记录和第1 1个记个记录的关键字比较为止。上述过程称作第一录的关键字比较为止。上述过程称作第一趟冒泡排序，其结果使得关键字最小的记趟冒泡排

12、序，其结果使得关键字最小的记录录“漂移漂移”到第一个记录的位置上。到第一个记录的位置上。16o然后进行其次趟冒泡排序，对后然后进行其次趟冒泡排序，对后n-1n-1个记录进行同样操作，其结果是使关个记录进行同样操作，其结果是使关键字次小的记录键字次小的记录“漂移漂移”到第到第2 2个记个记录的位置上。录的位置上。o，重复上述过程，直到，重复上述过程，直到“在一趟在一趟排序过程中没有进行过交换记录的操排序过程中没有进行过交换记录的操作作”为止。为止。17例例49 38 65 97 76 13 27 30初初始始关关键键字字38 49 65 76 13 27 30 97第第一一趟趟38 49 65

13、13 27 30 76第第二二趟趟38 49 13 27 30 65第第三三趟趟38 13 27 30 49第第四四趟趟13 27 30 38第第五五趟趟13 27 30第第六六趟趟38497697139727971376767627301365276530651313494930492738273830383018算法描述与分析算法描述与分析l起泡排序的效率，若初始序列为起泡排序的效率，若初始序列为“正正序序”，则只需进行一趟排序，在排序，则只需进行一趟排序，在排序过程中进行过程中进行n-1n-1次关键字间的比较；次关键字间的比较；反之，若初序列反之，若初序列“逆序逆序”，则需进行，则需进行

14、n-1n-1趟排序，需进行趟排序，需进行 次比较。并作等数量级的记录移动，次比较。并作等数量级的记录移动，因此，总的时间困难度为因此，总的时间困难度为O O（n2n2）。）。19二、快速排序二、快速排序 l其基本思想是其基本思想是：通过一趟排序将待：通过一趟排序将待排序记录分割成独立的两部分，其排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个两部分记录进行排序，以达到整个序列有序。序列有序。20l由此，可以该由此，可以该“枢轴枢轴”记录最终所落的位置最作分界线，将

15、记录最终所落的位置最作分界线，将序列序列L.rs，L.rs+1，L.rt分割成两个子序列分割成两个子序列L.rs，L.rs+1，L.ri-1和和 L.ri+1，L.ri+2，L.rt，这个过程称作一趟快速排序。，这个过程称作一趟快速排序。l一趟快速排序的具体做法是：对一趟快速排序的具体做法是：对rst中记录进行一趟快速中记录进行一趟快速排序，附设两个指针排序，附设两个指针low和和high，它们的初值分别为，它们的初值分别为low和和high，设枢轴记录的关键字为，设枢轴记录的关键字为Pivotkey，l然后从然后从low所指位置起向后搜寻找到第一个关键字大于所指位置起向后搜寻找到第一个关键字

16、大于Pivotkey的记录和枢轴记录相互交换做，重复这两步直至的记录和枢轴记录相互交换做，重复这两步直至low=high。l首先从首先从high所指位置起向前搜寻找到第一个关键字小于所指位置起向前搜寻找到第一个关键字小于Pivotkey的记录和枢轴记录相互交换，的记录和枢轴记录相互交换，21X 初始关键字：初始关键字：49 38 65 97 76 13 27 50lowhigh4927lowhighlowhighlowhigh6549lowhigh4913lowhigh9749lowhighlowhigh 完成一趟排序：完成一趟排序：(27 38 13)49(76 97 65 50)22分别进

17、行快速排序分别进行快速排序(13)27(38)49(50 65)76(97)快速排序结束：快速排序结束：13 27 38 49 50 65 7623l通常，快速排序平均时间困难度为通常，快速排序平均时间困难度为O(nlogn)，但待排序记录的，但待排序记录的键值几乎已排序时，状况反而恶化，每一趟快速排序的基准记键值几乎已排序时，状况反而恶化，每一趟快速排序的基准记录位置就是第一个记录位置或最终一个记录位置。最坏状况下录位置就是第一个记录位置或最终一个记录位置。最坏状况下的时间困难度为的时间困难度为T(n)=O(n)。l快速排序的平均时间为快速排序的平均时间为Tavg(n)=knlnn，其中，其

18、中n为待排序序列记为待排序序列记录的个数，录的个数，k为某个常数，阅历证明，在全部同数量级的此类为某个常数，阅历证明，在全部同数量级的此类（先进的）排序方法中，快速排序的常数因子（先进的）排序方法中，快速排序的常数因子k最小。因此，就最小。因此，就平均时间而言，快速排序是目前被认为是最好的一种内部排序平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。方法。l快速排序递归算法须要栈空间来实现递归，一般状况下须要的空快速排序递归算法须要栈空间来实现递归，一般状况下须要的空间为间为S(n)=O(log2n)，最坏状况下，须要的栈空间为，最坏状况下，须要的栈空间为S(n)=O(n)。l快速排

19、序方法是不稳定的快速排序方法是不稳定的。249.3 9.3 选择排序选择排序一、简洁选择排序一、简洁选择排序二、树形选择排序二、树形选择排序三、堆排序三、堆排序25一、简洁选择排序一、简洁选择排序l一趟简洁选择排序的操作为：通过一趟简洁选择排序的操作为：通过n-1n-1次次关键字的比较，从关键字的比较，从n n个记录中选择出关键个记录中选择出关键字最小的记录，并和第字最小的记录，并和第1 1个记录交换。个记录交换。l再通过再通过n-2n-2次比较，从剩余的次比较，从剩余的n-1n-1个记录个记录中找出关键字次小的记录，将它与第中找出关键字次小的记录，将它与第2 2个记录交换个记录交换l重复上述

20、操作，共进行重复上述操作，共进行n-1n-1趟排序后，趟排序后，排序结束排序结束.26初始：初始：49 38 65 97 76 13 27 jkkkkkkjji=11349一趟一趟:13 38 65 97 76 49 27 i=2jjkkkkk2738二趟二趟:13 27 65 97 76 49 38 三趟三趟:13 27 38 97 76 49 65 27五趟五趟:13 27 38 49 6513 27 38 49 65 97 76 97 76 六趟六趟:13 27 38 49 65 7613 27 38 49 65 76 97 97 排序结束排序结束:13 27 38 49 65 76 9

21、713 27 38 49 65 76 97四趟四趟:13 27 38 49 76 97 65 28o简洁选择排序过程中，所需进行记录移简洁选择排序过程中，所需进行记录移动的操作次数较少，其最小值为动的操作次数较少，其最小值为0 0，最大，最大值为值为3(n-1)3(n-1)。然而，无论记录的初始排列。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数如何，所需进行的关键字间的比较次数相同，均为相同，均为(n(n-1)/2(n(n-1)/2。因此，总的时间。因此，总的时间困难度也是困难度也是 O O（n2n2）。）。算法描述与算法评价算法描述与算法评价29二、树形选择排序二、树形选择排序

22、l树形选择排序，又称锦标赛排序，是一种树形选择排序，又称锦标赛排序，是一种依据锦标赛的思想进行选择排序的方法依据锦标赛的思想进行选择排序的方法l首先对首先对n n个记录的关键字进行两两比较，个记录的关键字进行两两比较，然后在其中然后在其中 n/2n/2 个较小者之间再进行个较小者之间再进行两两比较，如此重复，直至选出最小关两两比较，如此重复，直至选出最小关键字的记录为止。键字的记录为止。30386549977613274938651327381313树形选择排序示例树形选择排序示例31树形选择排序示例树形选择排序示例3865499776 274938657627382727输出输出1313之后

23、之后32树形选择排序示例树形选择排序示例3865499776 4938657649384938输出输出1313、2727之后之后33或或(i=1,2,.n/2)ki k2iki k2i+1ki k2iki k2i+1三、堆排序三、堆排序2 2、堆和完全二叉树、堆和完全二叉树 堆顶元素（或完全二叉树的根）必为序堆顶元素（或完全二叉树的根）必为序列中列中n n个元素的最小值（或最大值）个元素的最小值（或最大值）1、堆的定义、堆的定义 n个元素的序列个元素的序列(k1,k2,kn)，当且仅，当且仅当满足下列关系时，称之为堆当满足下列关系时，称之为堆34例例 （13,38,27,50,76,65,49

24、,97）1327384965765097353 3、堆排序、堆排序：若在输出堆顶的最小值之：若在输出堆顶的最小值之后，使得剩余后，使得剩余n-1n-1个元素的序列重又个元素的序列重又建成一个堆，则可得到建成一个堆，则可得到n n个元素的次个元素的次小值；如此反复执行，便能得到一个小值；如此反复执行，便能得到一个有序序列，这个过程称之为有序序列，这个过程称之为堆排序堆排序。l实现堆排序需解决的两个问题实现堆排序需解决的两个问题l如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？l如何在输出堆顶元素之后，调整剩余元如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？素，使之成为一个

25、新的堆？l二个问题解决方法二个问题解决方法筛选筛选364 4、筛选、筛选 13273849657650979727384965765013输出：输出：13372749389765765013输出：输出：139749382765765013输出：输出：13 27383849502765769713输出：输出：13 276549502738769713输出：输出：13 27 38394965502738769713输出：输出：13 27 387665502738499713输出：输出：13 27 38 49405065762738499713输出：输出：13 27 38 4997657627384

26、95013输出：输出：13 27 38 49 50416597762738495013输出：输出：13 2738 49 509765762738495013输出：输出：13 2738 49 50 65427665972738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 3849 50 65 76 97435 5、建堆、建堆 l建堆：从无序序列的第建堆：从无序序列的第 n/2n/2 个个元素（即此无序序列对应的完全元素（即此无序序列对应的完全二叉树的最终一个非终端结点）二叉树的最终一个非终端结点）起，至第一个元素止，进行反

27、复起，至第一个元素止，进行反复筛选筛选4449653827137697504965382713765097例如例如 含含8 8个元素的无序序列个元素的无序序列（49，38，65，97，76，13，27，50）45491338276576509749133827657650971349492746l时间困难度：最坏状况下时间困难度：最坏状况下T(n)=O(nlogn)T(n)=O(nlogn)l空间困难度：空间困难度：S(n)=O(1)S(n)=O(1)l总共进行的比较的次数为：总共进行的比较的次数为：2(2(log2(n-log2(n-1)1)+log2(n-log2(n-2)2)+log22

28、)2n(+log22)2n(log2nlog2n)由此，由此，堆排序在最坏的状况下，其时间困难度堆排序在最坏的状况下，其时间困难度为为O(nlogn)O(nlogn)。47初始关键字初始关键字:49386597 761327一趟归并后：一趟归并后：38 4965 9713 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 49 65 76 979.4 9.4 归并排序归并排序48l时间困难度：时间困难度：T(n)=O(nlog2n)T(n)=O(nlog2n)l空间困难度：空间困难度：S(n)=O(n)S(n)=O(n)l与快速

29、排序和堆排序相比，归并排序的与快速排序和堆排序相比，归并排序的最大特点，它是一种稳定的排序方法。最大特点，它是一种稳定的排序方法。但在一般状况下，很少利用但在一般状况下，很少利用2 2路归并排序路归并排序方法进行内部排序。方法进行内部排序。499.5 9.5 基数排序基数排序一、多关键字排序一、多关键字排序二、链式基数排序二、链式基数排序50l 2 3 A 2 3 Al 2 3 A 2 3 A一、多关键字排序一、多关键字排序l已知扑克牌中已知扑克牌中5252张牌面的次序为：张牌面的次序为：l两个关键字两个关键字：花色（：花色（）面值（面值（23A23A）l并且并且“花色花色”地位高于地位高于“

30、面值面值”51l方法方法1 1：先对花色排序，将其分为：先对花色排序，将其分为4 4个组，即梅花组、方块组、红心个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面组、黑心组。再对每个组分别按面值进行排序，最终，将值进行排序，最终，将4 4个组连接个组连接起来即可起来即可最高优先法最高优先法52方法方法2 2：先按先按1313个面值给出个面值给出1313个编号组个编号组(2(2号，号，3 3号，号，.，A A号号)，将牌按面值，将牌按面值依次放入对应的编号组，分成依次放入对应的编号组，分成1313堆。堆。再按花色给出再按花色给出4 4个编号组个编号组(梅花、方块、梅花、方块、红心、黑心红

31、心、黑心)，将，将2 2号组中牌取出分别号组中牌取出分别放入对应花色组，再将放入对应花色组，再将3 3号组中牌取号组中牌取出分别放入对应花色组出分别放入对应花色组,这样，这样，4 4个花色组中均按面值有序，然后，个花色组中均按面值有序，然后，将将4 4个花色组依次连接起来即可个花色组依次连接起来即可最低位优先法最低位优先法53l一般状况下，假设有一般状况下，假设有n n个记录的序列个记录的序列R1R1，R2R2，RnRn，且每个记录，且每个记录RiRi中含有中含有d d个关键字（个关键字（Ki0Ki0，Ki1Ki1，Kid-1Kid-1），则），则称序列对关键字（称序列对关键字（K0K0，K1

32、K1，Kd-1Kd-1）有序是指：对于序列中随意两个记录有序是指：对于序列中随意两个记录RiRi和和RjRj（1 1 ij ij n n）都满足下列有序关系）都满足下列有序关系（Ki0，Ki1，Kid-1）（Kj0，Kj1，Kjd-1）其中其中K K0 0称为称为最主位关键字最主位关键字，K Kd-1d-1称为称为最最次位关键字次位关键字。54o为实现多关键字排序，通常有两种方为实现多关键字排序，通常有两种方法：法：o(1)(1)先对最高位关键字进行排序先对最高位关键字进行排序(MSD)(MSD)o 最高优先法最高优先法o(2)(2)先对最凹凸关键字进行排序先对最凹凸关键字进行排序(LSD)(

33、LSD)o 最低位优先法最低位优先法55l第一种方法是先对最高位关键字第一种方法是先对最高位关键字K0（如花色）进行排序，（如花色）进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同将序列分成若干子序列，每个子序列中的记录都具有相同的的K0值；值；l然后分别就每个子序列对次关键字然后分别就每个子序列对次关键字K1（如面值）进行排序，（如面值）进行排序，按按K1值不同再分成若干更小的子序列；值不同再分成若干更小的子序列；l依次重复，直至对依次重复，直至对Kd-2进行排序之后得到的每一子序列中进行排序之后得到的每一子序列中的记录都具有相同的关键字（的记录都具有相同的关键字（K0，K1，K

34、d-2），而），而后分别每个子序列对后分别每个子序列对Kd-1进行排序，最终将全部子序列依进行排序，最终将全部子序列依次联接在一起成为一个有序序列，这种方法称之为最高优次联接在一起成为一个有序序列，这种方法称之为最高优先法（先法（Most Significant Digit first）（MSD)。56l其次种方法是从最低位关键字其次种方法是从最低位关键字Kd-1起进行排序。然后再对高一位的关键字起进行排序。然后再对高一位的关键字Kd-2排序，排序，依次重复，直至对最高位关键字依次重复，直至对最高位关键字K0排序后，便成为一个有序序列。排序后，便成为一个有序序列。这种方法称之为最低位优先法这种

35、方法称之为最低位优先法(LSD)。lMSDMSD与与LSDLSD不同特点不同特点l按按MSDMSD排序，必需将序列逐层分割成若干子排序，必需将序列逐层分割成若干子序列，然后对各子序列分别排序。序列，然后对各子序列分别排序。l按按LSDLSD排序，不必分成子序列，对每个关键排序，不必分成子序列，对每个关键字都是整个序列参与排序；并且可不通过关字都是整个序列参与排序；并且可不通过关键字比较，而通过若干次键字比较，而通过若干次“安排安排”与与“收集收集”实现排序。实现排序。57二、链式基数排序二、链式基数排序l基数排序：借助基数排序：借助“安排安排”和和“收集收集”对对单逻辑关键字进行排序的一种方法

36、单逻辑关键字进行排序的一种方法 l链式基数排序链式基数排序：用链表作存储结构的基：用链表作存储结构的基数排序数排序l逻辑关键字可以看成由若干个关键字复逻辑关键字可以看成由若干个关键字复合而成的。合而成的。58l由于如此分解而得的每个关键字由于如此分解而得的每个关键字Kj都在相同的范围内都在相同的范围内（对数字，（对数字，0Kj9，对字母，对字母“A”KjZ”），按），按LSD进行排序更为便利，只要从最小数位关键字起，按进行排序更为便利，只要从最小数位关键字起，按关键字的不同值将序列中记录关键字的不同值将序列中记录“安排安排”到到RADIX个队伍个队伍中后再中后再“收集收集”之，如此重复之，如此

37、重复d次。次。l按这种方法实现排序称之为基数排序，其中按这种方法实现排序称之为基数排序，其中“基基”指的指的是是RADIX的取值范围，在上述两种关键字的状况下，它的取值范围，在上述两种关键字的状况下，它们分别是们分别是“10”和和“26”。l首先以静态链表存储首先以静态链表存储n个待排记录，并令表头指针指向第个待排记录，并令表头指针指向第一个记录，如图一个记录，如图(a)所示。所示。59l第一趟安排对最低数位关键字（个位数）进行，变更记录第一趟安排对最低数位关键字（个位数）进行，变更记录的指针值将链表中的记录安排至的指针值将链表中的记录安排至10个链对列中去，每个队个链对列中去，每个队列中的记

38、录关键字的个位数相等，如图列中的记录关键字的个位数相等，如图(b)所示。所示。l其中其中fi和和ei分别为第分别为第i个队列的头指针和尾指针；个队列的头指针和尾指针；l第一趟收集是变更全部非空队列的对尾记录的指针值域，第一趟收集是变更全部非空队列的对尾记录的指针值域，令其指向下一个非空队列的对头的记录，重新将令其指向下一个非空队列的对头的记录，重新将10个队列个队列中的记录链成一个链表，如图（中的记录链成一个链表，如图（c）所示；）所示；l其次趟安排，其次趟收集及第三趟安排和第三趟收集分别其次趟安排，其次趟收集及第三趟安排和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图是对十

39、位数和百位数进行的，其过程和个位数相同，如图(d)(g)所示，至此排序完毕。所示，至此排序完毕。60初始状态初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：链式基数排序举例链式基数排序举例61505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6

40、e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：62008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：63l算法评价算法评价l时间困难度：安排：时间困难度：安排：T(n)=O(n)l收集：收集：T(n)=O(rd)l

41、 T(n)=O(d(n+rd)l空间困难度：空间困难度：S(n)=2rd个队列指针。个队列指针。+n个指针域空间个指针域空间l对于对于n个记录（假设每个记录含有个记录（假设每个记录含有d个关键字，每个关键字的个关键字，每个关键字的取值范围为取值范围为rd个值，进行链式基数排序的时间困难度为个值，进行链式基数排序的时间困难度为O(d(n+rd)，其中每一趟安排的时间困难度为，其中每一趟安排的时间困难度为O(n)，每一趟收，每一趟收集的时间困难度为集的时间困难度为O(rd)，整个排序需进行，整个排序需进行d趟安排和收集。趟安排和收集。l其中：其中：ln记录数记录数ld关键字数关键字数lrd关键字取

42、值范围关键字取值范围 649.6 9.6 各种内部排序方法的比较探讨各种内部排序方法的比较探讨排序方法排序方法 平均时间平均时间 最坏情况最坏情况 辅助存储辅助存储简单排序简单排序O(nO(n2 2)O(nO(n2 2)O(1)O(1)快速排序快速排序 O(nlogn)O(nlogn)O(nO(n2 2)O(logn)O(logn)堆排序堆排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(1)O(1)归并排序归并排序 O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n)O(n)基数排序基数排序 O(n(d+rO(n(d+rd)d)O(n(d+rO(n(

43、d+rd)d)O(rd)O(rd)65l从上表可以得出如下结论：从上表可以得出如下结论：（1）从平均时间性能而言，快速排序最佳，其所需时间最省，）从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏状况下的时间性能不如堆排序和归并排序。但快速排序在最坏状况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在而后两者相比较的结果是，在n较大时，归并排序所需时间较大时，归并排序所需时间较堆排序省，但它所需的协助存储量最多。较堆排序省，但它所需的协助存储量最多。（2）上表中的）上表中的“简洁排序简洁排序”包括除希尔排序之外的全部插入包括除希尔排序之外的全部插入排序，起泡排序和简

44、洁选择排序，其中以干脆插入排序为最排序，起泡排序和简洁选择排序，其中以干脆插入排序为最简洁，当序列中的记录简洁，当序列中的记录“基本有序基本有序”或或n值较小时，它是最值较小时，它是最佳的排序方法，因此常将它和其它的排序方法，诸如快速排佳的排序方法，因此常将它和其它的排序方法，诸如快速排序、归并排序等结合起来运用。序、归并排序等结合起来运用。66（3）基数排序的时间困难度也可写成）基数排序的时间困难度也可写成O(nd)。因此，它最。因此，它最适合用于适合用于n值很大而关键字较小的序列。若关键字也很大，值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的而序列中大多数记录的“最高位关键

45、字最高位关键字”均不同，则也可均不同，则也可先按先按“最高位关键字最高位关键字”不同将序列分成若干不同将序列分成若干“小小”的子序的子序列，而后进行干脆插入排序。列，而后进行干脆插入排序。（4）从方法的稳定性来比较，基数排序是稳定的内排方法，）从方法的稳定性来比较，基数排序是稳定的内排方法，全部时间困难度为全部时间困难度为O(n2)的简洁排序也是稳定的，然而，的简洁排序也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。都是不稳定的。671 1、对于给定的键值序列、对于给定的键值序列1212，2 2，1616，30

46、30，8 8，2828，4 4，1010分别写出干脆插入分别写出干脆插入排序、折半插入排序、希尔排序、干脆排序、折半插入排序、希尔排序、干脆选择排序、起泡排序的过程，并算出比选择排序、起泡排序的过程，并算出比较和记录移动次数。较和记录移动次数。第第9 9章章 作业作业682 2、对于给定的键值序列、对于给定的键值序列4141，6262，1313，8484，3535，9696，5757，3939，7979，6161，1515，8383，分别写出快速排序、归，分别写出快速排序、归并排序、堆排序的各趟排序结果。并排序、堆排序的各趟排序结果。3 3、本章介绍的内部排序方法中，哪几、本章介绍的内部排序方

47、法中，哪几种是稳定的？哪几种是不稳定的？种是稳定的？哪几种是不稳定的？69一、单项选择题一、单项选择题1 1、排序方法中，从未排序序列中依次取出元素与已排序序列、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为正确位置上的方法，称为 （A A）希尔排序）希尔排序 （B B）冒泡排序）冒泡排序 （C C）插入排序）插入排序 （DD）选择排序）选择排序2 2、在文件、在文件“局部有序局部有序”或文件长度较小的状况下，最佳内排或文件长度较小的状况下，最佳内排序方法是序方法是

48、 （A A）干脆插入排序）干脆插入排序 （B B）冒泡排序）冒泡排序 （C C）干脆选择排序）干脆选择排序 （D D）归并排序）归并排序第第9 9章章 作业作业703 3、对给出的一组关键字、对给出的一组关键字1414，5 5，1919，2020，1111，1919。若按关。若按关键字非递减排序，第一趟排序结果为键字非递减排序，第一趟排序结果为1414，5 5，1919，2020，1111，1919，问接受的排序算法是，问接受的排序算法是（A A）简洁选择排序）简洁选择排序 （B B）快速排序）快速排序 （C C）希尔排序）希尔排序 （DD）二路归并排序）二路归并排序4 4、在全部排序方法中，

49、关键字比较的次数与记录的初始排列、在全部排序方法中，关键字比较的次数与记录的初始排列次序无关的是次序无关的是 （A A）希尔排序）希尔排序 （B B）冒泡排序）冒泡排序 （C C）插入排序）插入排序 （D D）选择排序）选择排序71二、填空题二、填空题1、在对一组记录、在对一组记录54，38，96，23，15，72，60，45，83进进行干脆插入排序时，当把第行干脆插入排序时，当把第7个记录个记录60插入到有序表时，为找插入到有序表时，为找寻插入位置需比较寻插入位置需比较 次。次。2、每次干脆或通过基准元素间接比较两个元素，若出现逆序排、每次干脆或通过基准元素间接比较两个元素，若出现逆序排列时

50、就交换它们的位置，此种排序方法叫做列时就交换它们的位置，此种排序方法叫做 排序；排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。排序。3、排序方法接受的是二分法的思想，排序方法接受的是二分法的思想，排序方法排序方法其数据的组织接受完全二叉树结构。其数据的组织接受完全二叉树结构。72第第9 9章章 上机实习题上机实习题基本要求基本要求（1）选依次存储结构存放待排序的记录。输入并存放）选依次存储结构存放待排序的记录。输入并存放n个待个待排序的记录排序的记录（2）分别用堆排序、快速排序和归并排序方法，对待排序）分别用堆排序、快速排