《数据结构与算法》课件chap10.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第十章 内部 排序,,目录,10．1 基本概念,10．2 插入排序,,10,．,3,交换排序,,10．4 选择排序,10．5 归并排序,10．6 基数排序,,10．1 基本概念,,10.1.1 排序介绍,排序（,Sorting）,是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程表,10-1,学生档案表,,学号,,姓名,,年龄,,性别,,99001,,王晓佳,,18,,男,,99002,,林一鹏,,19,,男,,99003,,谢宁,,17,,女,,99004,,张丽娟,,18,,女,,99005,,周涛,,20,,男,,99006,,李小燕,,16,,女,,,例如，在表10-1中，若以每个记录的学号为关键字，按排序码年龄的递增（由小到大）排序，则所有记录的排序结果可简记为,：,,{（99006，16），（99003，17），（99001，18），（99004，18），（99002，19），（99005，20）}；,也可能为：,,{（99006，16），（99003，17），（99004，18），（99001，18），（99002，19），（99005，20）}；,,这两个结果都是表9-1按年龄的递增排序结果。

若按排序码姓名来进行递增排序，则得到的排序结果为：,,{（99006，李小燕），（99002，林一鹏），（99001，王晓佳），（99003，谢宁），（99004，张丽娟），（99005，周涛）},,当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析10.1.2,基本概念,,1．,排序码（,Sort Key）,,作为排序依据的记录中的一个属性它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字,如上例中的学生年龄在此我们认为对任何一种记录都可找到一个取得它排序码的函数,Skey,(,一个或多个关键字的组合)2．有序表与无序表,,一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表3．正序表与逆序表,,若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表不失普遍性，我们一般只讨论正序表4．排序定义,,若给定一组记录序列,r1 ，r2 ，…，,rn,，,其排序码分别为,s1，s2 ，…，,sn,，,将这些记录排成顺序为,rk1 ，rk2 ，…，,rkn,的一个序列,R’，,满足条件,sk1≤sk2≤ …≤,skn,，,获得这些记录排成顺序为,rp1 ，rp2 ，…，,rpn,的一个序列,R”，,满足条件,sp1≤sp2≤ …≤,spn,的过程称为排序。

也可以说，将一组记录按某排序码递增或递减排列的过程，称为排序5．稳定与不稳定,,因为排序码可以不是记录的关键字，同一排序码值可能对应多个记录对于具有同一排序码的多个记录来说，,若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的,在上例中（见表9-1，按年龄排序），如果一种排序方法使排序后的结果必为前一个结果，则称此方法是稳定的；若一种排序方法使排序后的结果可能为后一个结果，则称此方法是不稳定的6．内排序与外排序,,按照排序过程中使用内外存的不同将排序方法分为内排序和外排序若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序,内排序大致可分为五类：,插入排序、交换排序、选择排序、归并排序和分配排序本章仅讨论内排序7．排序的时间复杂性,,排序过程主要是对记录的排序码进行比较和记录的移动过程,因此排序的时间复杂性可以以,算法执行中的数据比较次数及数据移动次数,来衡量当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。

为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列排序,,插入排序（直插排序、二分排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序 （直选排序、树型排序、堆排序）,归并排序（二路归并排序、多路归并排序）,分配排序 （多关键字排序、基数排序）,,10．2 插入排序,,10.2.1,直接插入排序,,1．直接插入排序的基本思想,直接插入排序（,Straight Insertion Sorting）,的基本思想是,：,把,n,个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有,n-1,个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表2．直接插入的算法实现,,void sort(NODE array[],,int,n),,//,待排序元素用一个数组,array[ ],表示，数组有,n,个元素,,{,int,i, j;,,NODE x; // x,为中间结点变量,,,for ( i=1; i=0)&& ( x.key

它的直接插入排序的执行过程如图7-1所示3．直接插入排序的效率分析,从上面的叙述可以看出，直接插入排序算法十分简单那么它的效率如何呢？首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换从时间分析，首先外层循环要进行,n-1,次插入，每次插入最少比较一次（正序），移动两次；最多比较,i,次，移动,i＋2,次（逆序）（,i=1，2，…，n-1）因此，直接插入排序的时间复杂度为,O（n,2,）直接插入算法的元素移动是顺序的，该方法是稳定的10.2.3,希尔排序,,1,．希尔排序的基本思想,希尔排序,,,又称为“缩小增量排序”,是,1959,年由,D.L.Shell,提出来的该方法的基本思想是：,先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序,因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高2,．希尔排序的效率分析,,虽然我们给出的算法是三层循环，最外层循环为,log,2,n,数量级，中间的,for,循环是,n,数量级的，内循环远远低于,n,数量级，因为当分组较多时，组内元素较少；此循环次数少；当分组较少时，组内元素增多，但已接近有序，循环次数并不增加。

因此，希尔排序的时间复杂性在,O（nlog,2,n）,和,O（n,2,）,之间，大致为,O（n,1. 3,）例如，,n=8，,数组,array[ ],的八个元素分别为：91，67，35，62，29，72，46，57下面用图10-2给出希尔排序算法的执行过程由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此,希尔排序是不稳定的10,．,3,交换排序,10.3.1,冒泡排序,,1．冒泡排序的基本思想,通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒,因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志,flag,判断元素是否进行过交换从而减少不必要的比较2．冒泡排序的算法实现,,void,Bubblesort,( NODE array[],,int,n),,{,int,i, j, flag;,,//,当,flag,为0则停止排序,,,NODE temp;,,for ( i=1; i=i; j--),,if (array[j].key

下面用图10-3给出冒泡排序算法的执行过程3．冒泡排序的效率分析,,从上面的例子可以看出，当进行完第三趟排序时，数组已经有序，所以第四趟排序的交换标志为0，即没进行交换，所以不必进行第四趟排序从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（,n-1）,次，移动元素次数为0；若待排序的元素为逆序，则需进行,n-1,趟排序，比较次数为(,n,2,-n)/2，,移动次数为3(,n,2,-n )/2，,因此冒泡排序算法的时间复杂度为,O（n,2,）由于其中的元素移动较多，所以属于内排序中速度较慢的一种因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法10.3.2,,快速排序,,1,．快速排序的基本思想,快速排序（,Quick Sorting）,是迄今为止所有内排序算法中速度最快的一种,它的基本思想是：,任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序,快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。

快速排序的过程为：把待排序区间按照第一个元素（即基准元素）的排序码分为左右两个子序列的过程叫做一次划分设待排序序列为,array[start]～array[end]，,其中,start,为下限，,end,为上限，,start＜end，mid=array[start],为该序列的基准元素，为了实现一次划分，令,i,j,的初值分别为,start,和,end在划分过程中，首先让,j,从它的初值开始，依次向前取值，并将每一元素,array[j],的排序码同,mid,的排序码进行比较，直到,array[j].key

此次划分得到的前后两个待排序的子序列分别为,array[start]～array[i-1],和,array[i+1]～array[end]例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图10-4所示从图7-4可知，通过一次划分，将一个区间以基准值分成两个子区间，左子区间的值小于等于基准值，右子区间的值大于基准值对剩下的子区间重复此划分步骤，则可以得到快速排序的结果2．快速排序的算法实现,,下面给出快速排序算法的递归算法如下：,,void,quicksort,(NODE array[],,int,start ,,int,end),,{,int,i , j; NODE mid;,,if (start>=end) return;,,i=start;j=end;mid=array[i];,,while (i

因此，快速排序的最好时间复杂度应为,O（nlog,2,n）而且在理论上已经证明，快速排序的平均时间复杂度也为,O（nlog,2,n）若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有,n-i,个(,i,代表二叉树的层数（1≤,i≤n）,元素，每层划分需要比较,n-i+2,次，所以总的比较次数为（,n,2,+3n-4）/2因此，快速排序的最坏时间复杂度为,O(n,2,)快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为,O（log,2,n），,最坏的空间复杂度为,O(n)快速排序是一种不稳定的排序方法7．4 选择排序,,7.4.1 直接选择排序,,1．直接选择排序的基本思想,直接选择排序也是一种简单的排序方法它的基本思想是：,第一次从,array[0]~array[n-1],中选取最小值，与,array[0],交换，第二次从,array[1]~array[n-1],中选取最小值，与,array[1],交换，第三次从,array[2]~array[n-1],中选取最小值，与,array[2],交换，…，第,i,次从,array[i-1]~array[n-1],中选取最小值，与,array[i-1],交换，…, 第,n-1,次从,array[n-2]~array[n-1],中选取最小值，与,array[n-2],交换，总共通过,n-1,次，得到一个按排序码从小到大排列的有序序列。

例如，给定,n=8，,数组,R,中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示3．直接选择排序的效率分析,,在直接选择排序中，共需要进行,n-1,次选择和交换，每次选择需要进行,n-i,次比较（1≤,i≤n-1），,而每次交换最,,多需3次移动，因此，总的比较次数,C= =(n,2,-n)/2，,,总的移动次数,M= =3(n-1)由此可知，直接选择,,排序的时间复杂度为,O(n,2,),数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法例如，给定排序码为3，7，,3,，2，1，排序后的结果为1，2，,3,，3，77.4.2,树形选择排序,,从直接选择排序可知，在,n,个排序码中，找出最小值需,n-1,次比较，找出第二小值需,n-2,次比较，找出第三小值需,n-3,次比较，其余依此类推所以，总的比较次数为：(,n-1)+(n-2)+…+3+2+1= (n,2,-n)/2，,那么，能否对直接选择排序算法加以改进，使总的比较次数比 (,n,2,-n)/2,小呢？显然，在,n,个排序码中选出最小值，至少进行,n-1,次比较，但是，继续在剩下的,n-1,个关键字中选第二小的值，就并非一定要进行,n-2,次比较，若能利用前面,n-1,次比较所得信息，则可以减少以后各趟选择排序中所用的比较次数，比如8个运动员中决出前三名，不需要7+6+5=18场比赛（前提是，若甲胜乙，而乙胜丙，则认为甲胜丙），最多需要11场比赛即可（通过7场比赛产生冠军后，第二名只能在输给冠军的三个对中产生，需 2场比赛，而第三名只能在输给亚军的三个对中产生，也需2场比赛，总共11场比赛）。

具体见图7-6所示从图10-6（,a）,可知，8个队经过4场比赛，获胜的4个队进入半决赛，再经过2场半决赛和1场决赛即可知道冠军属谁（共7场比赛）按照锦标赛的传递关糸，亚军只能产生于分别在决赛，半决赛和第一轮比赛中输给冠军的选取手中，于是亚军只能在,b、c、e,这3个队中产生（见图7-6（,b）），,即进行2场比赛（,e,与,c,一场，,e,与,c,的胜队与,b,一场）后，即可知道亚军属谁同理，第三名只需在,c、f、g,这3个队产生（见图7-6（,c））,即进2场比赛（,f,与,g,一场，,f,与,g,的胜队与,c,一场）即可知道第三名属谁树形选择排序,，,又称锦标赛排序,，,是一种按照锦标赛的思想进行选择排序的方法首先对,n,个记录的排序码进行两两比较，然后在其中,,n/2,,,个较小者之间再进行两两比较，如此重复，直到选出最小排序码为止例如，给定排序码头 50，37，66，98，75，12，26，49，树形选择排序过程见图7-710.4.3,堆排序,,1．堆的定义,,若有,n,个元素的排序码,k,1,，k,2,，k,3,，…，,k,n,，,当满足如下条件：,,,k,i,≤k,2i,k,i,≥k,2i,,（1）,k,i,≤k,2i+1,,或 (2),k,i,≥k,2i+1,,,其中,i=1,2,…,,,n/2,,,则称此,n,个元素的排序码,k,1,，k,2,，k,3,，…，,k,n,为一个堆。

若将此排序码按顺序组成一棵完全二叉树，则（1）称为小根堆（,二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）若将此排序码按顺序组成一棵完全二叉树，则（1）称为小根堆（,二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）Ri,R2i,R2i+1,堆顶元素,左子树为堆,右子,树为堆,,,若,n,个元素的排序码,k,1,，k,2,，k,3,，…，,k,n,满足堆，且让结点按1、2、3、…、,n,顺序编号，根据完全二叉树的性质（若,i,为根结点，则左孩子为2,i，,右孩子为2,i+1）,可知，堆排序实际与一棵完全二叉树有关若将排序码初始序列组成一棵完全二叉树，则堆排序可以包含,建立初始堆,（使排序码变成能符合堆的定义的完全二叉树）和,利用堆进行排序,两个阶段例如：定义一维数组,,,int,S[11]={12,36,27,65,40,34,98,81,73,55,49},,0,1,2,3,4,5,6,7,8,9,10,11,,12,36,27,65,40,34,98,81,73,55,49,S,,,2．堆排序的基本思想,,将排序码,k,1,，k,2,，k,3,，…，,k,n,表示成一棵完全二叉树，然后从第,,n/2,,,个排序码(即树的最后一个非终端结点)开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第,,n/2,,-1,个排序码重复刚才操作，直到第一个排序码止。

这时候，该二叉树符合堆的定义，初始堆已经建立接着，可以按如下方法进行堆排序：将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（,k,1,与,k,n,），,再将,k,1,~,k,n,-1,重新建堆，然后,k,1,和,k,n,-1,交换，再将,k,1,~,k,n,-2,重新建堆，然后,k,1,和,k,n,-2,交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止这时堆排序已经完成，则排序码,k,1,，k,2,，k,3,，…，,k,n,已排成一个有序序列例如，给定排序码49，38，65，97，76，13，27，70，建立初始堆的过程如图7-8所示建成如图7-8(,e),所示的堆后，堆排序过程如图7-9所示按层次遍历完全二叉树，得到一个由大到小排列的有序序列：,,97，76，70，65，49，38，27，13,,4．堆排序的效率分析,,在整个堆排序中，共需要进行,n+,,n/2,,-1,次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度，所以，每次筛选运算的时间复杂度为,O(log,2,n)，,故整个堆排序过程的时间复杂度为,O(nlog,2,n)。

堆排序占用的辅助空间为1（供交换元素用），故它的空间复杂度为,O（1）堆排序是一种不稳定的排序方法，例如，给定排序码：2，1，,2,，它的排序结果为：1，,2,，210．5 归并排序,10.5.1 二路归并排序,,二路归并排序的基本思想,二路归并排序的基本思想是：,将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到,n（,元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结果例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示3．二路归并排序的效率分析,,二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积而归并趟数为,,log,2,n,,(,当,,log,2,n,,,为奇数时，则为,,log,2,n,,+1)因为每一趟归并就是将两两有序子区间合并成一个有序子区间，而每一对有序子区间归并时，记录的比较次数均小于等于记录的移动次数（即由一个数组复制到另一个数组中的记录个数），而记录的移动次数等于这一对有序表的长度之和，所以，每一趟归并的移动次数均等于数组中记录的个数,n，,即每一趟归并的时间复杂度为,O(n)。

因此，二路归并排序的时间复杂度为,O(nlog,2,n)利用二路归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为,O(n)，,比前面介绍的其它排序方法占用的空间大由于二路归并排序中，每两个有序表合并成一个有序表时，若分别在两个有序表中出现有相同排序码，则会使前一个有序表中相同排序码先复制，后一有序表中相同排序码后复制，从而保持它们的相对次序不会改变所以，二路归并排序是一种稳定的排序方法10.6 基 数 排 序,,,基数排序,是一种借助,“多关键字排序”的思想来实现,“单关键字排序”的内部排序算法,多关键字的排序,链式基数排序,,一、多关键字的排序,,n,,个记录的序列,{,R,1,, R,2,,,…,，,R,n,},,对关键字,(,K,i,0,, K,i,1,,,…,,K,i,d-1,),有序,是指：,其中,:,K,0,被称为,“最主”位关键字,K,d-1,被称为,“,最次”位关键字,,对于序列中任意两个记录,R,i,,和,R,j,,(1,≤,i

先对,K,d-1,进行排序，然后对,K,d-2,进行排序，依次类推，,直至对最主位关键字,K,0,排序完成为止,排序过程中不需要根据,“,前一个,”,关键字的排序结果，将记录序列分割成若干个,(,“,前一个,”,关键字不同的,),子序列例如,:,学生记录含三个关键字,:,,系别,、,班号,和,班内的序列号,，其中以系别为最主位关键字无序序列,对,K,2,排序,对,K,1,排序,对,K,0,排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,,15,2,3,,18,3,1,,20,2,1,,20,3,2,,30,3,,1,,20,2,,1,,20,1,,2,,15,3,,2,,30,2,,3,,18,,1,,2,15,2,,1,20,2,,3,18,3,,1,20,3,,2,30,LSD,的排序过程如下,:,,二、链式基数排序,,假如多关键字的记录序列中，每个关键字的取值范围相同，则按,LSD,法进行排序时，可以采用,“,分配,-,收集,”,的方法，其,好处是不需要进行关键字间的比较,对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种,“,分配,-,收集,”,的办法进行排序，称作基数排序法。

例如：,对下列这组关键字,,,{209, 386, 768, 185, 247, 606, 230, 834, 539 },,首先按其 “个位数” 取值分别为 0, 1, …, 9,“分配”,成 10 组，之后按从 0 至 9 的顺序将 它们,“收集”,在一起；,,然后按其 “十位数” 取值分别为 0, 1, …, 9,“分配”,成 10 组，之后再按从 0 至 9,的顺序将它们,“收集”,在一起；,最后按其“百位数”重复一遍上述操作在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：,,１．,待排序记录以指针相链，构成一个链表；,２,．“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同；,３,．,“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;,４．,对每个关键字位均重复,2),和,3),两步例如：,p,→,369,→,367,→,167,→,239,→,237,→,138,→,230,→,139,进行第一次分配,进行第一次收集,f[,0,] r[,0,],f[7] r[,7,],f[,8,] r[,8,],f[,9,] r[,9,],p→230,→23,0,←,→36,7,←,→16,7,→23,7,→367→167→237,→138,→368→239→139,→36,9,←,→23,9,→13,9,→13,8,←,,进行第二次分配,p→230→237→138→239→139,p→230→367→167→237→138→368→239→139,f[,3,] r[,3,],f[,6,] r[,6,],→2,3,0 ←,→2,3,7,→1,3,8,→2,3,9,→1,3,9,→3,6,7 ←,→1,6,7,→3,6,8,→367→167→368,进行第二次收集,,,进行第三次收集之后便得到记录的有序序列,f[,1,] r[,1,],p→230→237→138→239→139→367→167→368,进行第三次分配,f[,2,] r[,2,],f[,3,] r[,3,],→,1,38 ←,→,1,39,→,1,67,→,2,30 ←,→,2,37,→,2,39,→,3,67 ←,→,3,68,p→138→139→167,→230→237→239,→367→368,,提醒注意：,１．,“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；,２．为查找使用，该链表尚需应用算法,Arrange,将它调整为有序表。

基数排序的时间复杂度为,O(d(n+rd)),其中：分配为,O(n),,,,收集为,O(rd),(,rd,为“基”),,,,d,为“分配-收集”的趟数,,10,．,7,各种内排序方法的比较和选择,,10.7.1,各种内排序方法的比较,,1．从时间复杂度比较,从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为,O(n,2,)，,而快速排序、堆排序、二路归并排序的时间复杂度都为,O(nlog,2,n)，,希尔排序的复杂度介于这两者之间若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为,O(n)，,其它的最好情形同平均情形相同若从最坏的时间复杂度考虑，则快速排序的为,O(n,2,)，,直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大2．从空间复杂度比较,,归并排序的空间复杂度最大，为,O(n)，,快速排序的空间复杂度为,O(log,2,n)，,其它排序的空间复杂度为,O（1）3.从稳定性比较,,直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。

4．从算法简单性比较,,直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解10.7.2,各种内排序方法的选择,,1．从时间复杂度选择,,对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法2．从空间复杂度选择,,尽量选空间复杂度为,O（1）,的排序方法，其次选空间复杂度为,O(log,2,n),的快速排序方法，最后才选空间复杂度为,O（n）,二路归并排序的排序方法3．一般选择规则,,（1）,,当待排序元素的个数,n,较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜2)当待排序元素的个数,n,大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜3）当待排序元素的个数,n,大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜4,),当待排序元素的个数,n,小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜5)当待排序元素的个数,n,小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。

冒泡排序一般很少采用返回目录,,。