第九章 排序.ppt

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

1、第第9章章 排序排序9.1 排序的基本概念排序的基本概念9.2 插入排序插入排序9.3 交换排序交换排序9.4 归并排序归并排序9.5 基数排序基数排序9.6 各种排序算法的性能比较各种排序算法的性能比较本章主要知识点：本章主要知识点：排序的基本概念和衡量排序算法优劣的标准，排序的基本概念和衡量排序算法优劣的标准，其中衡量标准有算法的时间复杂度、空间复杂其中衡量标准有算法的时间复杂度、空间复杂度和稳定性度和稳定性直接插入排序，希尔排序直接插入排序，希尔排序直接选择排序，堆排序直接选择排序，堆排序冒泡排序，快速排序冒泡排序，快速排序归并排序归并排序基数排序基数排序各种排序算法的性能比较各种排序算

2、法的性能比较9.1 排序的基本概念排序的基本概念 排序排序是对数据元素序列建立某种有序排列的过程。是对数据元素序列建立某种有序排列的过程。关键关键字是要排序的数据元素集合中的一个域，排序字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。是以关键字为基准进行的。关键字关键字分分主关键字主关键字和和次关键字次关键字两种。对要排序的数两种。对要排序的数据元素集合来说，如果关键字满足数据元素值不同时据元素集合来说，如果关键字满足数据元素值不同时该关键字的值也一定不同，这样的关键字称为该关键字的值也一定不同，这样的关键字称为主关键主关键字字。不满足主关键字定义的关键字称为不满足主关键字定义

3、的关键字称为次关键字。次关键字。学生成绩表学生成绩表排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集中，存在假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的多个具有相同键值的记录，若经过排序，这些记录的相对次序相对次序仍然保持不变，即在原序列中，仍然保持不变，即在原序列中，ki=kj且且ri在在rj之前，之前，而在排序后的序列中，而在排序后的序列中，ri仍在仍在rj之前，则称这种之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法是稳定的；否则称为不稳定的。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明649

4、20003汤晓影汤晓影8586687278 排序排序分分内部排序内部排序和和外部排序外部排序两种。两种。内部排序内部排序是是把待排数据元素全部调入内存中进行的排序。如把待排数据元素全部调入内存中进行的排序。如果数据元素的数量太大，需要分批导入内存，分果数据元素的数量太大，需要分批导入内存，分批导入内存的数据元素排好序后再分批导出到磁批导入内存的数据元素排好序后再分批导出到磁盘和磁带外存介质上的排序方法称作盘和磁带外存介质上的排序方法称作外部排序外部排序。排序算法的比较标准：排序算法的比较标准：1.空间复杂度空间复杂度 2.时间复杂度时间复杂度 3.稳定性稳定性内排序的方法分为五类：内排序的方法

5、分为五类：插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序基数排序基数排序若无特别声明，假定是按关键字若无特别声明，假定是按关键字递增递增排排序，且以序，且以顺序表顺序表作为表的存储结构。作为表的存储结构。插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次将一个待排序的记录按其关键码的大小插每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部入到一个已经排好序的有序序列中，直到全部记录排好序为止。记录排好序为止。9.2 插入排序插入排序9.2.1 直插入排序直插入排序 直接插入排序直接插入排序的基本思想是：顺序地把待

6、排的基本思想是：顺序地把待排序的数据元素按其值的大小插入到已排序数据元序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大。当子集合大小只有一个数据元素开始逐次增大。当子集合大小最终和集合大小相同时排序完毕。最终和集合大小相同时排序完毕。基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已个记录已经排好序。经排好序。直接插入排序直接插入排序直接插入排序直接插入排序有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+

7、1r r1r r2r ri-1r rir rnr ri+1（1）如何构造初始的有序序列？）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置?需解决的关键问题需解决的关键问题?直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例直接插入排序过程示例 1 2 3 4 5 62121181825252222101025*25*21212121252518182222101025*25*252518182222101025*25*25252222212125252121151510102525*25252121151510102525*252521211

8、818151510101818101025*25*181818182525*i=0i=1i=2i=3i=4初始关键字初始关键字解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起个记录起依次插入到这个有序表中，直到将第依次插入到这个有序表中，直到将第n个记录插入。个记录插入。直接插入排序直接插入排序直接插入排序直接插入排序关键问题关键问题(1)如何构造初始的有序序列？如何构造初始的有序序列？算法描述：算法描述：for(i=0;i-1&temp=aj)aj+1=aj;j-;a j+1 =temp;直接插入排序直接插入排序直接插入排序直接插入排序

9、public static void insertSort(int a)int i,j,temp;int n=a.length;for(i=0;i -1&temp aj)aj+1=aj;j-;aj+1=temp;直接插入排序算法直接插入排序算法直接插入排序算法直接插入排序算法public static void main(String args)int test=64,5,7,89,6,24;int n=test.length;insertSort(test);for(int i=0;i n;i+)System.out.print(testi+);直接插入排序算法的测试程序直接插入排序算法的测

10、试程序直接插入排序算法的测试程序直接插入排序算法的测试程序直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好最好情况下（正序）：情况下（正序）：比较次数：比较次数：n-1移动次数：移动次数：2(n-1)最坏最坏情况下（逆序或反序）：情况下（逆序或反序）：时间复杂度为时间复杂度为O(n2)。5 54 43 32 21 14 45 53 32 21 13 34 45 52 21 12 23 34 45 51 11 12 23 34 45 54 43 32 21 1比较次数：比较次数：移动次数：移动次数：2)1(0-=nn(i+1)n-2i2)1)(

11、4(3-+=+nnin-20=i）（时间复杂度为时间复杂度为O(n)。平均平均情况下（随机排列）：情况下（随机排列）：数据元素的比较和移动次数都约为数据元素的比较和移动次数都约为n n2 2/4/4 直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析时间复杂度为时间复杂度为O(n2)。空间性能：空间性能：需要一个记录的辅助空间，需要一个记录的辅助空间，空间复杂度为空间复杂度为O（1）。）。直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算

12、法性能分析原始数据元素集合越接近有序，直接插入排序算法原始数据元素集合越接近有序，直接插入排序算法的时间效率越高，其时间效率在的时间效率越高，其时间效率在O(n)到到O(n2)之间。之间。当待排序的记录个数较多时，大量的比较和移动操当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。作使直接插入排序算法的效率降低。直接插入排序算法简单、容易实现，适用于待排序直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较少时。记录基本有序或待排序记录较少时。以上结论是希尔排序算法成立的基础。以上结论是希尔排序算法成立的基础。9.2.2 希尔排序希尔排序 对直接插入

13、排序算法改进的着眼点：对直接插入排序算法改进的着眼点：（1）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直接插入时，直接插入排序的效率可以大大提高；排序的效率可以大大提高；（2）由于直接插入排序算法简单，则在待排序记录）由于直接插入排序算法简单，则在待排序记录数量数量n较小较小时效率也很高。时效率也很高。希尔排序希尔排序的基本思想是：把待排序的数据元素分的基本思想是：把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小；当完成接插入法排序；小组的个数逐次缩小；当完成了所有数据元素都在一个组内的排序

14、后排序过了所有数据元素都在一个组内的排序后排序过程结束。希尔排序又称作程结束。希尔排序又称作缩小增量排序缩小增量排序。需解决的关键问题需解决的关键问题?（1）应如何分割待排序记录，才能保证整个序列逐步）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？向基本有序发展？（2）子序列内如何进行直接插入排序？）子序列内如何进行直接插入排序？基本有序基本有序：接近正序，例如：接近正序，例如1,2,8,4,5,6,7,3,9；局部有序局部有序：部分有序，例如：部分有序，例如6,7,8,9,1,2,3,4,5。局部有序不能提高直接插入排序算法的时间性能。局部有序不能提高直接插入排序算法的时间性能。

15、分割待排序记录的目的分割待排序记录的目的?1.减少待排序记录个数；减少待排序记录个数；2.使整个序列向基本有序发展。使整个序列向基本有序发展。子序列的构成不能是简单地子序列的构成不能是简单地“逐段分割逐段分割”，而是将相，而是将相距某个距某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。启示启示?希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4 5 6 7 8 9404021212525494925*25*1616初始序列初始序列303008081313d=4404021212525494925*25*16163030080813132

16、5252 21 125*25*303008084949131316164040d=2131325252 21 1080825*25*16163030494940402525212125*25*303008081313161640404949d=1080825252121131325*25*16163030404049490808252513131616212125*25*404030304949解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。到目

17、前为到目前为止增量的选取无一定论止增量的选取无一定论,但无论增量序列如何选取但无论增量序列如何选取,最后一个增量必须等于最后一个增量必须等于1。关键问题关键问题(1)(1)应如何分割待排序记录？应如何分割待排序记录？希尔插入排序希尔插入排序希尔插入排序希尔插入排序解决方法：解决方法：在插入记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为d）搜索待插入位置。当搜索位置搜索待插入位置。当搜索位置0，表示插，表示插入位置已找到。入位置已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。在整个序列中，前在整个序列中，前d个记录分别

18、是个记录分别是d个子序列中的第个子序列中的第一个记录，所以从第一个记录，所以从第d+1个记录开始进行插入。个记录开始进行插入。关键问题关键问题(2)子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？希尔插入排序希尔插入排序希尔插入排序希尔插入排序 将记录序列分成若干子序列，分别对每个子序列进行将记录序列分成若干子序列，分别对每个子序列进行插入排序。插入排序。其中，其中，d 称为增量，它的值在排序过程中从大到小逐称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为渐缩小，直至最后一趟排序减为 1。例如：将例如：将 n 个记录分成个记录分成 d 个子序列：个子序列：R0，R

19、d，R2d，Rkd R1，R1+d，R1+2d，R1+kd Rd-1，R2d-1，R3d-1，R(k+1)d-1 例如：例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量第一趟希尔排序，设增量 d=511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量第二趟希尔排序，设增量 d=39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量第三趟希尔排序，设增量 d=1 9 11 12 16 18 23 25 30 31 36 47 public static void shellSort(in

20、t a,int d,int numOfD)int i,j,k,m,span;int temp;int n=a.length;for(m=0;m numOfD;m+)/共共numOfD次循环次循环span=dm;/取本次的增量值取本次的增量值for(k=0;k span;k+)/共共span个小组个小组for(i=k;i -1&temp=aj)aj+span=aj;j=j-span;aj+span=temp;for(i=span;in;i+)temp=ai;j=i-span;希尔排序测试程序：希尔排序测试程序：public static void main(String args)int tes

21、t=65,34,25,87,12,38,56,46,14,77,92,23;int n=test.length;int numOfD=3;int d=6,3,1;shellSort(test,d,numOfD);for(int i=0;i ai+1，则交换两个数据元，则交换两个数据元素，否则不交换，这样数值最大的数据元素将被放置在素，否则不交换，这样数值最大的数据元素将被放置在an-1中。中。p第第2趟时，循环次数减趟时，循环次数减1，即数据元素个数为，即数据元素个数为n-1，操作方法，操作方法和第和第1趟的类似，这样整个趟的类似，这样整个n个数据元素集合中数值次大的数个数据元素集合中数值次大

22、的数据元素将被放置在据元素将被放置在an-2中。中。p当第当第n-1趟结束时，整个趟结束时，整个n个数据元素集合中次小的数据元素个数据元素集合中次小的数据元素将被放置在将被放置在a1中，中，a0中放置了最小的数据元素。中放置了最小的数据元素。0505989812126969383853538181冒泡排序过程示例冒泡排序过程示例冒泡排序过程示例冒泡排序过程示例 0505989812126969383853538181050598981212696938385353818105059898121269693838535381810505989812126969383853538181解决方法：解

23、决方法：在算法中设计一个在算法中设计一个flagflag变量，用于标记本次排序过程是否有变量，用于标记本次排序过程是否有交换动作，若本次排序过程没有交换动作则说明数据元素集交换动作，若本次排序过程没有交换动作则说明数据元素集合已全部排好序，可提前结束排序过程。合已全部排好序，可提前结束排序过程。在每一趟起泡排序之前，令在每一趟起泡排序之前，令flagflag的初值为的初值为0，在以后的排序过在以后的排序过程中，只要有记录交换，程中，只要有记录交换，flag就赋值为就赋值为1，这样，在一趟比较这样，在一趟比较完毕，就可以通过完毕，就可以通过flag 的值是否为的值是否为0来判别是否有记录交换，来

24、判别是否有记录交换，从而判别整个起泡排序的结束。从而判别整个起泡排序的结束。关键问题：有时并不需要关键问题：有时并不需要 n-1 n-1 趟冒泡，数据元素就已经全部排趟冒泡，数据元素就已经全部排列就绪，如列就绪，如判别起泡排序的结束？判别起泡排序的结束？冒泡排序算法冒泡排序算法:public static void bubbleSort(int a)int i,j,flag=1;int temp;int n=a.length;for(i=1;i n&flag=1;i+)flag=0;for(j=0;j aj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;起泡排序的时间性

25、能分析起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 1 12 23 34 45 5时间复杂度为时间复杂度为O(n)。1 12 23 34 45 5最坏情况（反序）：最坏情况（反序）：起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 5 54 43 32 21 1时间复杂度为时间复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。4 43 32 21 15 53 32

26、 21 14 45 52 21 13 34 45 51 12 23 34 45 5比较次数：比较次数：移动次数：移动次数：2)1(1-=nn(n-i)n-1i2)1(1-=n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时间复杂度为O(n2)。9.4.2 9.4.2 9.4.2 9.4.2 快速快速快速快速排序排序排序排序改进的着眼点：改进的着眼点：在起泡排序中，记录的比较和移动是在起泡排序中，记录的比较和移动是在在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多

27、。减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面快速排序快速排序算法的基本思想是：设数组算法的基本思想是：设数组a中存放了中存放了n个数据元素，个数据元素，low为数组的低端下标，为数组的低端下标，high为数组的高端下标，从数组为数组的高端下标，从数组a中中任取一个元素做为任取一个元素做为标准元素标准元素，以该标准元素调整数组，以该标准元素调整数组a中其他中其他各个元素的位置，使排在标准元素前面的元素均小于标准元各个元素的位置，

28、使排在标准元素前面的元素均小于标准元素，排在标准元素后面的均大于或等于标准元素。这样一次素，排在标准元素后面的均大于或等于标准元素。这样一次排序过程结束后，一方面将标准元素放在了未来排好序的数排序过程结束后，一方面将标准元素放在了未来排好序的数组中该组中该标准元素应位于的位置标准元素应位于的位置上，另一方面将数组中的元素上，另一方面将数组中的元素以标准元素为中心分成了两个子数组，位于标准元素左边子以标准元素为中心分成了两个子数组，位于标准元素左边子数组中的元素均数组中的元素均小于小于标准元素，位于标准元素右边子数组中标准元素，位于标准元素右边子数组中的元素均的元素均大于等于大于等于或标准元素。

29、对这两个子数组中的元素分或标准元素。对这两个子数组中的元素分别再进行方法类同的别再进行方法类同的递归快速排序递归快速排序。算法的递归出口条件是。算法的递归出口条件是lowhigh。选择标准元素的方法：选择标准元素的方法：1.使用第一个记录的关键码；使用第一个记录的关键码；2.选取序列中间记录的关键码；选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为标准元素并记录的关键码，取关键码居中的作为标准元素并调换到第一个记录的位置；调换到第一个记录的位置；4.随机选取标准元素。随机选取标准元素。关键问题关键问题

30、：如何选择标准元素？如何选择标准元素？选取不同标准元素的后果：选取不同标准元素的后果：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。1313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555关键问题关键问题(2)(2)：如何实现一次划分？如何实现一次划分？jjiiijijjj解决方法：解决方法：设待划分的序列是设待划分的序列是rs rt，设参数设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令令rs为轴值，

31、为轴值，（1）j从后从后向前向前扫描，直到扫描，直到rjri，将将rj移动到移动到ri的位置，使关键码小（同轴值相比）的记录移动到前的位置，使关键码小（同轴值相比）的记录移动到前面去；面去；（2）i从前从前向后向后扫描，直到扫描，直到rirj，将将ri移动到移动到rj的位置，使关键码大（同轴值比较）的记录移动到后的位置，使关键码大（同轴值比较）的记录移动到后面去；面去；（3）重复上述过程，直到）重复上述过程，直到i=j。关键问题关键问题(2)(2)：如何实现一次划分？如何实现一次划分？解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。关键问

32、题关键问题：如何处理分割得到的两个待排序子序列？：如何处理分割得到的两个待排序子序列？13132727383865655050494955551313272750503838494955556565ijijpublic static void quickSort(int a,int low,int high)int i,j;int temp;i=low;j=high;temp=alow;/取第一个元素为标准数据元素取第一个元素为标准数据元素while(i j)while(i j&temp=aj)j-;/在数组的右端扫描在数组的右端扫描if(i j)ai=aj;i+;while(i j&ai t

33、emp)i+;/在数组的左端扫描在数组的左端扫描if(i j)aj=ai;j-;ai=temp;if(low i)quickSort(a,low,i-1);/对左端子集合递归对左端子集合递归if(i high)quickSort(a,j+1,high);/对右端子集合递归对右端子集合递归快速排序算法描述：快速排序算法描述：最坏情况：最坏情况：每次划分只得到一个比上一次划分少一个记录的子序列（另一每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为个子序列为空），为 O(n2)。最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与右侧子表每一次划分对一个记录定位

34、后，该记录的左侧子表与右侧子表的长度相同，为的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析平均情况：平均情况：为为O(nlog2n)。)()1(21211nOnninni=-=-=）（注意：快速排序算法的平均时间复杂度与最好时间复杂度。注意：快速排序算法的平均时间复杂度与最好时间复杂度。9.5 归并排序归并排序 归并排序归并排序主要是二路归并排序。二路归并排序的基本思主要是二路归并排序。二路归并排序的基本思想是：设数组想是：设数组a中存放了中存放了n个数据元素，初始时我们把它们看个数据元素，初始时我们把它们看成是成是n个长度为个长度为1的有序子数组，然后从第一个

35、子数组开始，的有序子数组，然后从第一个子数组开始，把相临的子数组两两合并，得到把相临的子数组两两合并，得到n/2个（若个（若n/2为小数则上取整）为小数则上取整）长度为长度为2的新的有序子数组（当的新的有序子数组（当n为奇数时最后一个新的有序为奇数时最后一个新的有序子数组的长度为子数组的长度为1）；对这些新的有序子数组再两两归并；如）；对这些新的有序子数组再两两归并；如此重复，直到得到一个长度为此重复，直到得到一个长度为n的有序数组为止。多于二路的的有序数组为止。多于二路的归并排序方法和二路归并排序方法类同。归并排序方法和二路归并排序方法类同。二路二路归并排序归并排序算法各次归并排序过程算法各

36、次归并排序过程 9.6 基数排序基数排序 基数排序基数排序算法的基本思想是：设待排序的数据元素是算法的基本思想是：设待排序的数据元素是m位位d进制整数（不足进制整数（不足m位的在高位补位的在高位补0），设置），设置d个桶，令个桶，令其编号分别为其编号分别为0,1,2,d-1。首先按最低位（即个位）的数值。首先按最低位（即个位）的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这素，这

37、样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；再对一次基数排序得到样的一次排序过程为一次基数排序；再对一次基数排序得到的数据元素序列按次低位（即十位）的数值依次把各数据元的数据元素序列按次低位（即十位）的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程元素的先后次序收集分配在各桶中的数据元素；这样的过程重复进行，当完成了第重复进行，当完成了第m次基数排序后，就得到了排好序的次基数排序后，就得到了排好序的数据元素序列。数据元素序列。9.7 各种排序算法的性能比较各种排序算法的性能比较 排序方法最好时间 平均时间 最坏时间 辅助空间 稳定性 直接插入排序 O(n)O(n2)O(n2)O(1)稳定 希尔排序 O(n1.3)O(1)不稳定 直接选择排序 O(n2)O(n2)O(n2)O(1)稳定 堆排序 O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定冒泡排序 O(n)O(n2)O(n2)O(1)稳定快速排序 O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定归并排序 O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序 O(mn)O(mn)O(mn)O(n)稳定