第9章--排序总结

《第9章--排序总结》由会员分享，可在线阅读，更多相关《第9章--排序总结（72页珍藏版）》请在金锄头文库上搜索。

1、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直接插入排序的基本操作是将一个记录直接插入排序的基本操作是将一个记录插入到已排好的有序表中，从而得到一插入到已排好的有序表中，从而得到一个新的、记录数增加个新的、记录数增加1 1的有序表

2、。的有序表。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在含有在含有i-1i-1个记录

4、的有序子序列个记录的有序子序列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) 2727jjjjjj977665493827

6、 排序结果：排序结果：(13 27 38 49 65 76 (13 27 38 49 65 76 97)97)7l记录按关键字非递增有序排列时比较的次记录按关键字非递增有序排列时比较的次数达最大值数达最大值记录移动次数达到最大值记录移动次数达到最大值l关键字间的比较次数和移动记录的次数关键字间的比较次数和移动记录的次数, ,约为约为n n2 2 /4 /4。由此，直接插入排序的时间。由此，直接插入排序的时间复杂度为复杂度为O O（ n n2 2 ）。）。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 ) 20l

8、owhighmidi=8 20 (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排序过程：排序过程：先取一个正整数

9、先取一个正整数d d1 1nn，把全部，把全部记录分成若干个组，所有距离为记录分成若干个组，所有距离为d d1 1倍数的倍数的记录放一组，在各组内进行插入排序记录放一组，在各组内进行插入排序; ;然后然后取取d d2 2dd1 1，重复上述分组和排序工作，重复上述分组和排序工作; ;直至直至d di i=1=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

10、 27 48 55 449 38 65 97 76 13 27 48 55 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希尔排序所需的比较和移动次数

11、约为希尔排序所需的比较和移动次数约为n n1.31.3，当，当n n 时，可减少到时，可减少到n(logn(log2 2n)n)2 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初初始始关关键键字

13、字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第第六六趟趟38497697139727971376767627301365276530651313494930492738273830383018算法描述与分析算法描述与分析l起泡排序的效率，若初始序列为起泡排序的效率，若初始序列为“正序正序”，则只需进行一趟排序，在排，则只需进行一趟排序，在排序过程中进行序过程中进行n-1n-1次关键字间的比较；

14、次关键字间的比较；反之，若初序列反之，若初序列“逆序逆序”，则需进行，则需进行n-1n-1趟排序，需进行趟排序，需进行 次比较。并作等数量级的记录移动，次比较。并作等数量级的记录移动，因此，总的时间复杂度为因此，总的时间复杂度为O O（n n2 2）。）。19二、快速排序二、快速排序 l其基本思想是其基本思想是：通过一趟排序将待：通过一趟排序将待排序记录分割成独立的两部分，其排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个两部分记录进行排序，以达到整个序列有序。序

15、列有序。20l由此，可以该由此，可以该“枢轴枢轴”记录最后所落的位置最作分界线，将记录最后所落的位置最作分界线，将序列序列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然后从然后从

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

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

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

19、)，最坏情况下，需要的栈空间为，最坏情况下，需要的栈空间为S(n)=O(n)。l快速排序方法是不稳定的快速排序方法是不稳定的。249.3 9.3 选择排序选择排序一、简单选择排序一、简单选择排序二、树形选择排序二、树形选择排序三、堆排序三、堆排序25一、简单选择排序一、简单选择排序l一趟简单选择排序的操作为：通过一趟简单选择排序的操作为：通过n-1n-1次次关键字的比较，从关键字的比较，从n n个记录中选择出关键字个记录中选择出关键字最小的记录，并和第最小的记录，并和第1 1个记录交换。个记录交换。l再通过再通过n-2n-2次比较，从剩余的次比较，从剩余的n-1n-1个记录个记录中找出关键字次

20、小的记录，将它与第中找出关键字次小的记录，将它与第2 2个记录交换个记录交换l重复上述操作，共进行重复上述操作，共进行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 761

21、3 27 38 49 65 76 97 97 排序结束排序结束: :13 27 38 49 65 76 9713 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。因此，总的。因此，总的时间复杂度也是时间复

22、杂度也是 O O（n n2 2）。）。算法描述与算法评价算法描述与算法评价29二、树形选择排序二、树形选择排序l树形选择排序，又称锦标赛排序树形选择排序，又称锦标赛排序，是一种，是一种按照锦标赛的思想进行选择排序的方法按照锦标赛的思想进行选择排序的方法l首先对首先对n n个记录的关键字进行两两比较，个记录的关键字进行两两比较，然后在其中然后在其中 n/2n/2 个较小者之间再进行两个较小者之间再进行两两比较，如此重复，直至选出最小关键两比较，如此重复，直至选出最小关键字的记录为止。字的记录为止。30386549977613274938651327381313树形选择排序示例树形选择排序示例31

23、树形选择排序示例树形选择排序示例3865499776 274938657627382727输出输出1313之后之后32树形选择排序示例树形选择排序示例3865499776 4938657649384938输出输出1313、2727之后之后33或或(i=1,2,. n/2 )ki k2iki k2i+1ki k2iki k2i+1三、堆排序三、堆排序2 2、堆和完全二叉树、堆和完全二叉树 堆顶元素（或完全二叉树的根）必为序堆顶元素（或完全二叉树的根）必为序列中列中n n个元素的最小值（或最大值）个元素的最小值（或最大值）1、堆的定义、堆的定义 n n个元素的序列个元素的序列(k(k1 1,k,k

24、2 2, ,k kn n) )，当且仅，当且仅当满足下列关系时，称之为堆当满足下列关系时，称之为堆34例例 （13,38,27,50,76,65,49,97）1327384965765097353 3、堆排序、堆排序：若在输出堆顶的最小值之：若在输出堆顶的最小值之后，使得剩余后，使得剩余n-1n-1个元素的序列重又个元素的序列重又建成一个堆，则可得到建成一个堆，则可得到n n个元素的次个元素的次小值；如此反复执行，便能得到一个小值；如此反复执行，便能得到一个有序序列，这个过程称之为有序序列，这个过程称之为堆排序堆排序。l实现堆排序需解决的两个问题实现堆排序需解决的两个问题l如何由一个无序序列建

25、成一个堆？如何由一个无序序列建成一个堆？l如何在输出堆顶元素之后，调整剩余如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？元素，使之成为一个新的堆？l二个问题解决方法二个问题解决方法筛选筛选364 4、筛选、筛选 13273849657650979727384965765013输出：输出：13372749389765765013输出：输出：139749382765765013输出：输出：13 27383849502765769713输出：输出：13 276549502738769713输出：输出：13 27 38394965502738769713输出：输出：13 27 387665

26、502738499713输出：输出：13 27 38 49405065762738499713输出：输出：13 27 38 499765762738495013输出：输出：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/2

27、n/2 个元个元素（即此无序序列对应的完全二素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选至第一个元素止，进行反复筛选4449653827137697504965382713765097例如例如 含含8 8个元素的无序序列个元素的无序序列（49，38，65，97，76，13，27，50）45491338276576509749133827657650971349492746l时间复杂度时间复杂度：最坏情况下：最坏情况下T(n)=O(nlogn)l空间复杂度：空间复杂度：S(n)=O(1)S(n)=O(1)l总共进行的比较的次

28、数为：总共进行的比较的次数为：2( log2(n-1) + log2(n-2) +log22)2n( log2n )由此，由此，堆堆排序在最坏的情况下，其时间复杂度为排序在最坏的情况下，其时间复杂度为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(nlogT(n)=O(nlog2 2n)n

29、)l空间复杂度：空间复杂度：S(n)=O(n)S(n)=O(n)l与快速排序和堆排序相比，归并排序的与快速排序和堆排序相比，归并排序的最大特点，它是一种稳定的排序方法最大特点，它是一种稳定的排序方法。但在一般情况下，很少利用但在一般情况下，很少利用2 2路归并排序路归并排序方法进行内部排序。方法进行内部排序。499.5 9.5 基数排序基数排序一、多关键字排序一、多关键字排序二、链式基数排序二、链式基数排序50l 2 3 A 2 3 Al 2 3 A 2 3 A一、多关键字排序一、多关键字排序l已知扑克牌中已知扑克牌中5252张牌面的次序为：张牌面的次序为：l两个关键字两个关键字：花色（：花色

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

31、出再按花色给出4 4个编号组个编号组( (梅花、方块、梅花、方块、红心、黑心红心、黑心) )，将，将2 2号组中牌取出分别号组中牌取出分别放入对应花色组，再将放入对应花色组，再将3 3号组中牌取号组中牌取出分别放入对应花色组出分别放入对应花色组, , ,这样，这样，4 4个花色组中均按面值有序，然后，个花色组中均按面值有序，然后，将将4 4个花色组依次连接起来即可个花色组依次连接起来即可最低位优先法最低位优先法53l一般情况下，假设有一般情况下，假设有n n个记录的序列个记录的序列RR1 1，R R2 2，R Rn n ，且每个记录，且每个记录R Ri i中含有中含有d d个关个关键字（键字（

32、K Ki0i0，K Ki1i1，K Kid-1id-1），则称序列对），则称序列对关键字（关键字（K K0 0，K K1 1，K Kd-1d-1）有序是指：对）有序是指：对于序列中任意两个记录于序列中任意两个记录R Ri i和和R Rj j（1 1 ij ij n n）都满足下列有序关系）都满足下列有序关系（Ki0，Ki1，Kid-1）（Kj0，Kj1，Kjd-1） 其中其中K K0 0称为称为最主位关键字最主位关键字，K Kd-1d-1称为称为最最次位关键字次位关键字。54o为实现多关键字排序，通常有两种方为实现多关键字排序，通常有两种方法：法：(1)(1)先对最高位关键字进行排序先对最高位

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

34、进行排序之后得到的每一子序列中的进行排序之后得到的每一子序列中的记录都具有相同的关键字（记录都具有相同的关键字（ K0，K1，Kd-2），而后分），而后分别每个子序列对别每个子序列对Kd-1进行排序，最后将所有子序列依次联接进行排序，最后将所有子序列依次联接在一起成为一个有序序列，这种方法称之为在一起成为一个有序序列，这种方法称之为最高优先法最高优先法（Most Significant Digit first） （MSD) 。56l第二种方法是从最低位关键字第二种方法是从最低位关键字Kd-1起进行排序。然后再对高一位的关键字起进行排序。然后再对高一位的关键字Kd-2排排序，序，依次重复，直至对

35、最高位关键字依次重复，直至对最高位关键字K0排序后，便成为一个有序序列。这排序后，便成为一个有序序列。这种方法称之为种方法称之为最低位优先法最低位优先法(LSD)。lMSDMSD与与LSDLSD不同特点不同特点l按按MSDMSD排序排序，必须将序列逐层分割成若干子，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。序列，然后对各子序列分别排序。l按按LSDLSD排序排序，不必分成子序列，对每个关键，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次键字比较，而通过若干次“分配分配”与与“收集收集”实现排序。实现排序

36、。57二、链式基数排序二、链式基数排序l基数排序基数排序：借助：借助“分配分配”和和“收集收集”对对单逻辑关键字单逻辑关键字进行排序的一种方法进行排序的一种方法 l链式基数排序链式基数排序：用链表作存储结构的基：用链表作存储结构的基数排序数排序l逻辑关键字可以看成由若干个关键字复逻辑关键字可以看成由若干个关键字复合而成的。合而成的。58l由于如此分解而得的每个关键字由于如此分解而得的每个关键字Kj都在相同的范围内都在相同的范围内（对数字，（对数字， 0 Kj 9，对字母，对字母“A” Kj Z”），按），按LSD进行排序更为方便，只要从最小数位关键字起，按关键进行排序更为方便，只要从最小数位关

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

38、位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至的指针值将链表中的记录分配至10个链对列中去，每个队个链对列中去，每个队列中的记录关键字的个位数相等，如图列中的记录关键字的个位数相等，如图(b)所示。所示。l其中其中fi和和ei分别为第分别为第i个队列的头指针和尾指针；个队列的头指针和尾指针；l第一趟收集是改变所有非空队列的对尾记录的指针值域，第一趟收集是改变所有非空队列的对尾记录的指针值域，令其指向下一个非空队列的对头的记录，重新将令其指向下一个非空队列的对头的记录，重新将10个队列个队列中的记录链成一个链表，如图（中的记录链成一个链表，如图（c）所示；）所示；l第二趟分配，第二

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

40、8109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：62008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184

41、589二趟收集：二趟收集：63l算法评价算法评价l时间复杂度：分配：时间复杂度：分配：T(n)=O(n)l收集：收集：T(n)=O(rd)l T(n)=O(d(n+rd)l空间复杂度空间复杂度：S(n)=2rd个队列指针。个队列指针。+n个指针域空间个指针域空间l对于对于n个记录（假设每个记录含有个记录（假设每个记录含有d个关键字，每个关键字的个关键字，每个关键字的取值范围为取值范围为rd个值，进行链式基数排序的时间复杂度为个值，进行链式基数排序的时间复杂度为O(d(n+rd)，其中每一趟分配的时间复杂度为，其中每一趟分配的时间复杂度为O(n)，每一趟收，每一趟收集的时间复杂度为集的时间复杂度

42、为O(rd)，整个排序需进行，整个排序需进行d趟分配和收集。趟分配和收集。l其中：其中：ln记录数记录数ld关键字数关键字数lrd关键字取值范围关键字取值范围 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(

43、nlogn)O(nlogn) O(nlogn)O(nlogn)O(n)O(n)基数排序基数排序 O(n(d+rdO(n(d+rd)O(n(d+rdO(n(d+rd)O(rd)O(rd)65l从上表可以得出如下结论：从上表可以得出如下结论：（1）从平均时间性能而言，快速排序最佳，其所需时间最省，从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在而后两者相比较的结果是，在n较大时，归并排序所需时间较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。较堆排序

44、省，但它所需的辅助存储量最多。（2）上表中的）上表中的“简单排序简单排序”包括除希尔排序之外的所有插入包括除希尔排序之外的所有插入排序，起泡排序和简单选择排序，其中以直接插入排序为最排序，起泡排序和简单选择排序，其中以直接插入排序为最简单，简单，当序列中的记录当序列中的记录“基本有序基本有序”或或n值较小时，它是最值较小时，它是最佳的排序方法，佳的排序方法，因此常将它和其它的排序方法，诸如快速排因此常将它和其它的排序方法，诸如快速排序、归并排序等结合起来使用。序、归并排序等结合起来使用。66（3）基数排序的时间复杂度也可写成）基数排序的时间复杂度也可写成O(nd)。因此，它最。因此，它最适合用

45、于适合用于n值很大而关键字较小的序列。若关键字也很大，值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的而序列中大多数记录的“最高位关键字最高位关键字”均不同，则也可均不同，则也可先按先按“最高位关键字最高位关键字”不同将序列分成若干不同将序列分成若干“小小”的子序的子序列，而后进行直接插入排序。列，而后进行直接插入排序。（4）从方法的稳定性来比较，基数排序是稳定的内排方法，）从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为所有时间复杂度为O(n2)的简单排序也是稳定的，然而，的简单排序也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法快速排序、堆

46、排序和希尔排序等时间性能较好的排序方法都是不稳定的。都是不稳定的。671 1、对于给定的键值序列、对于给定的键值序列1212，2 2，1616，3030，8 8，2828，4 4，1010分别写出直接插入排分别写出直接插入排序、折半插入排序、希尔排序、直接选序、折半插入排序、希尔排序、直接选择排序、起泡排序的过程，并算出比较择排序、起泡排序的过程，并算出比较和记录移动次数。和记录移动次数。第第9 9章章 作业作业682 2、对于给定的键值序列、对于给定的键值序列4141，6262，1313，8484，3535，9696，5757，3939，7979，6161，1515，8383，分别写出快速排

47、序、归并排序、，分别写出快速排序、归并排序、堆排序的各趟排序结果。堆排序的各趟排序结果。3 3、本章介绍的内部排序方法中，哪几、本章介绍的内部排序方法中，哪几种是稳定的？哪几种是不稳定的？种是稳定的？哪几种是不稳定的？69一、单项选择题一、单项选择题1 1、排序方法中，从未排序序列中依次取出元素与已排序序列、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为正确位置上的方法，称为 （A A）希尔排序）希尔排序 （B B）冒泡排序）冒泡排序 （C C）插入排序）插入排序

48、（D D）选择排序）选择排序2 2、在文件、在文件“局部有序局部有序”或文件长度较小的情况下，最佳内排或文件长度较小的情况下，最佳内排序方法是序方法是 （ 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，问采用的排序算法是，问采用的排序算法是（

49、A A）简单选择排序）简单选择排序 （B B）快速排序）快速排序 （C C）希尔排序）希尔排序 （D D）二路归并）二路归并排序排序4 4、在所有排序方法中，关键字比较的次数与记录的初始排列、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是次序无关的是 （ A A）希尔排序）希尔排序 （B B）冒泡排序）冒泡排序 （ C C）插入排序）插入排序 （ D D）选择排序）选择排序71二、填空题二、填空题1、在对一组记录、在对一组记录54，38，96，23，15，72，60，45，83进进行直接插入排序时，当把第行直接插入排序时，当把第7个记录个记录60插入到有序表时，为寻插入到有序表

50、时，为寻找插入位置需比较找插入位置需比较 次。次。2、每次直接或通过基准元素间接比较两个元素，若出现逆序排、每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做列时就交换它们的位置，此种排序方法叫做 排序；排序； 每次使两个相邻的有序表合并成一个有序表的排序方法叫做每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。排序。3、 排序方法采用的是二分法的思想，排序方法采用的是二分法的思想， 排序方法排序方法其数据的组织采用完全二叉树结构。其数据的组织采用完全二叉树结构。72第第9 9章章 上机实习题上机实习题基本要求基本要求（1）选顺序存储结构存放待排序的记录。输入并存放）选顺序存储结构存放待排序的记录。输入并存放n个待个待排序的记录排序的记录（2）分别用堆排序、快速排序和归并排序方法，对待排序）分别用堆排序、快速排序和归并排序方法，对待排序记录进行排序并输出排序结果。记录进行排序并输出排序结果。