数据结构课件第十章.ppt

《数据结构课件第十章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第十章.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程的内容数据结构课程的内容19.1 9.1 概述概述9.29.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 基数排序基数排序第第十十章章 内部排序内部排序210.1 10.1 概述概述1 1、排序是计算机内经常进行的一种操作，其目的是将一、排序是计算机内经常进行的一种操作，其目的是将一组组“无序无序”的记录序列调整为的记录序列调整为“按关键字有序按关键字有序”的记录序的记录序列。列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一

2、般情况下，一般情况下，假设含假设含n n个记录的序列为个记录的序列为R1R1，R2R2，RnRn 其相应的关键字序列为其相应的关键字序列为 K1K1，K2K2，KnKn 这些关键字相互之间可以进行比较，这些关键字相互之间可以进行比较，即在它们之间存在这样一个关系：即在它们之间存在这样一个关系：Kp1=Kp2=Kp1=Kp2=36)(42n/2时，表示结点i为叶子结点。35080825254646494958586767234561（大根堆）（大根堆）91918585666676765858676723456155557例：例：例：例：有序列有序列T1=（08,25,49,46,58,67）和序

3、列和序列T2=（91,85,76,66,58,67,55）,判断它们是否判断它们是否“堆堆”？（小根堆）（小根堆）（小顶堆）（小顶堆）（最小堆）（最小堆）（大顶堆）（大顶堆）（最大堆）（最大堆）36步骤：步骤：步骤：步骤：从最后一个从最后一个从最后一个从最后一个非终端结点非终端结点非终端结点非终端结点开始往前逐步调整，让每个双开始往前逐步调整，让每个双开始往前逐步调整，让每个双开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。亲大于（或小于）子女，直到根结点为止。亲大于（或小于）子女，直到根结点为止。亲大于（或小于）子女，直到根结点为止。2121252525*25*4949161

4、60808123456例：例：关键字序列关键字序列T=(21，25，49，25*，16，08），），请建请建大根堆大根堆。2.2.2.2.怎样建堆？怎样建堆？怎样建堆？怎样建堆？解：解：为便于理解，先将原始序列画成完全二叉树的形式：为便于理解，先将原始序列画成完全二叉树的形式：完全二叉树的第一个非终端结点完全二叉树的第一个非终端结点完全二叉树的第一个非终端结点完全二叉树的第一个非终端结点编号必为编号必为编号必为编号必为 n/2n/2n/2n/2 ！(性质性质性质性质5)5)5)5)注：注：终端结点（即叶子）没有任何子女，无需单独调整。终端结点（即叶子）没有任何子女，无需单独调整。2121i=3

5、:i=3:49大于大于08，不必调整；，不必调整；i=2:i=2:25大于大于25*和和16，也不必调整；，也不必调整；i=1:i=1:21小于小于25和和49，要调整！，要调整！4949而且而且21还应当向下比较！还应当向下比较！37关键：关键：关键：关键：将堆的当前顶点输出后，如何将剩余序将堆的当前顶点输出后，如何将剩余序将堆的当前顶点输出后，如何将剩余序将堆的当前顶点输出后，如何将剩余序列重新调整为堆？列重新调整为堆？列重新调整为堆？列重新调整为堆？方法：方法：方法：方法：将当前顶点将当前顶点将当前顶点将当前顶点与堆尾记录交换与堆尾记录交换与堆尾记录交换与堆尾记录交换，然后，然后，然后，

6、然后仿仿仿仿建建建建堆动作重新调整，如此反复直至排序结堆动作重新调整，如此反复直至排序结堆动作重新调整，如此反复直至排序结堆动作重新调整，如此反复直至排序结束。束。束。束。3.3.3.3.怎样进行堆排序？怎样进行堆排序？怎样进行堆排序？怎样进行堆排序？3808 25 21 25*16 08 25 21 25*16 4949交换交换交换交换 1 1号与号与号与号与 6 6 号记录号记录号记录号记录4949252525*25*21211616080812345649 25 21 25*16 0849 25 21 25*16 08初始最大堆初始最大堆初始最大堆初始最大堆252525*25*16162

7、12113654208084949例：例：例：例：对刚才建好的大根堆进行排序：对刚才建好的大根堆进行排序：对刚才建好的大根堆进行排序：对刚才建好的大根堆进行排序：3916 25*21 08 16 25*21 08 25 4925 49交换交换交换交换 1 1号与号与号与号与 5 5 号记录号记录号记录号记录0808 25 2125 21 25*16 25*16 4949从从从从 1 1 号到号到号到号到 5 5 号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆0808252525*25*212116164949123456161625*25*0808252521214

8、9491365420808252525*25*25 25 0808 21 21 25*16 25*16 4949080825 25 2525*2121 08 08 16 16 49494008 16 21 08 16 21 25*25*2525 49 49交换交换交换交换 1 1 号号号号与与与与 4 4 号记录号记录号记录号记录25*16 21 08 25*16 21 08 25 4925 49从从从从 1 1号到号到号到号到 4 4号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆25*25*161608082121252549491234560808161625*

9、25*2525212149491365424108 16 08 16 21 25*21 25*2525 49 49交换交换交换交换 1 1号与号与号与号与3 3 号记录号记录号记录号记录21 16 08 21 16 08 25*25*2525 49 49从从从从 1 1 号到号到号到号到 3 3号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆2121161625*25*0808252549491234560808161625*25*2525212149491365424208 08 16 21 25*16 21 25*2525 49 49交换交换交换交换 1 1 号与

10、号与号与号与2 2 号记录号记录号记录号记录16 08 16 08 2121 25*25*2525 49 49从从从从 1 1 号到号到号到号到 2 2 号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆1616080825*25*2121252549491234560808161625*25*252521214949136542439.5 9.5 归并排序归并排序归并排序的基本思想是：归并排序的基本思想是：归并排序的基本思想是：归并排序的基本思想是：将两个（或以上）的有序将两个（或以上）的有序将两个（或以上）的有序将两个（或以上）的有序表组成新的有序表。表组成新的有序

11、表。表组成新的有序表。表组成新的有序表。更实际的意义：更实际的意义：更实际的意义：更实际的意义：可以把一个长度为可以把一个长度为可以把一个长度为可以把一个长度为n n 的无序序列看成是的无序序列看成是的无序序列看成是的无序序列看成是 n n 个长度为个长度为个长度为个长度为 1 1 的有序子序列的有序子序列的有序子序列的有序子序列 ，首先做两两归并，得到，首先做两两归并，得到，首先做两两归并，得到，首先做两两归并，得到 n n/2/2 个长度为个长度为个长度为个长度为 2 2 的子序列的子序列的子序列的子序列 ；再做两两归并，；再做两两归并，；再做两两归并，；再做两两归并，如此重复，直到，如此

12、重复，直到，如此重复，直到，如此重复，直到最后得到一个长度为最后得到一个长度为最后得到一个长度为最后得到一个长度为 n n 的有序序列。的有序序列。的有序序列。的有序序列。例：例：例：例：关键字序列关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），），请给出归并排序的具体实请给出归并排序的具体实现过程。现过程。44lenlen=1=1lenlen=2=2lenlen=4=4lenlen=8=8lenlen=16=16整个归并排序仅需整个归并排序仅需整个归并排序仅需整个归并排序仅需 loglog2 2n n 趟趟趟趟45归并排序算法分析：归并排序算法分析：归并

13、排序算法分析：归并排序算法分析：时间效率：时间效率：时间效率：时间效率：O(O(n nloglog2 2n n)因因为为在在递递归归的的归归并并排排序序算算法法中中，函函数数Merge()做做一一趟趟两两路路归归并并排排序序，需需要要调调用用merge()函函数数 n/(2*len)O(n/len)次次，函函数数Merge()调调用用Merge()正正好好 log2n 次次，而而每每次次merge()要要执执行行比比较较O(len)次，所以算法总的时间复杂度为次，所以算法总的时间复杂度为O(nlog2n)。空间效率：空间效率：空间效率：空间效率：O(O(n n)因因为为需需要要一一个个与与原原

14、始始序序列列同同样样大大小小的的辅辅助助序序列列（TR）。这这正正是是此算法的缺点。此算法的缺点。稳定性：稳定性：稳定性：稳定性：稳定稳定稳定稳定469.6 9.6 基数排序基数排序 (Radix Sort)要讨论的问题：要讨论的问题：要讨论的问题：要讨论的问题：1.1.什么是什么是什么是什么是“多关键字多关键字多关键字多关键字”排序？实现方法？排序？实现方法？排序？实现方法？排序？实现方法？2.2.单逻辑关键字怎样单逻辑关键字怎样单逻辑关键字怎样单逻辑关键字怎样“按位值按位值按位值按位值”排序？排序？排序？排序？基数排序的基本思想是：基数排序的基本思想是：基数排序的基本思想是：基数排序的基本

15、思想是：借助多关键字排序的思想对单逻辑关键字进行排借助多关键字排序的思想对单逻辑关键字进行排借助多关键字排序的思想对单逻辑关键字进行排借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字序。即：用关键字序。即：用关键字序。即：用关键字不同的位值不同的位值不同的位值不同的位值进行排序。进行排序。进行排序。进行排序。471.1.什么是什么是什么是什么是“多关键字多关键字多关键字多关键字”排序？实现方法排序？实现方法排序？实现方法排序？实现方法？例例例例1 1：对一副扑克牌该如何排序？：对一副扑克牌该如何排序？：对一副扑克牌该如何排序？：对一副扑克牌该如何排序？若规定花色和面值的顺序关系为：若

16、规定花色和面值的顺序关系为：若规定花色和面值的顺序关系为：若规定花色和面值的顺序关系为：花色花色花色花色：面值：面值：面值：面值：2 3 4 5 6 7 8 9 10 J Q K A2 3 4 5 6 7 8 9 10 J Q K A 则则则则可以可以可以可以先按花色先按花色先按花色先按花色排序，花色相同者排序，花色相同者排序，花色相同者排序，花色相同者再按面值再按面值再按面值再按面值排序；排序；排序；排序；也可以先按面值排序，面值相同者再按花色排序。也可以先按面值排序，面值相同者再按花色排序。也可以先按面值排序，面值相同者再按花色排序。也可以先按面值排序，面值相同者再按花色排序。例例例例2

17、2 2 2：职工分房该如何排序？：职工分房该如何排序？：职工分房该如何排序？：职工分房该如何排序？河大规定：河大规定：河大规定：河大规定：先以总分先以总分先以总分先以总分排序（职称分工龄分）；排序（职称分工龄分）；排序（职称分工龄分）；排序（职称分工龄分）；总分相同者，总分相同者，总分相同者，总分相同者，再按配偶总分再按配偶总分再按配偶总分再按配偶总分排序，其次按配偶职排序，其次按配偶职排序，其次按配偶职排序，其次按配偶职称、工龄、人口称、工龄、人口称、工龄、人口称、工龄、人口等等排序。等等排序。等等排序。等等排序。以上两例都是典型的多关键字排序！48多多多多关键字排序的实现方法通常有两种：关

18、键字排序的实现方法通常有两种：关键字排序的实现方法通常有两种：关键字排序的实现方法通常有两种：最高位优先法最高位优先法最高位优先法最高位优先法MSD(Most Significant Digit first)MSD(Most Significant Digit first)例：例：例：例：对一副扑克牌该如何排序？对一副扑克牌该如何排序？对一副扑克牌该如何排序？对一副扑克牌该如何排序？答：答：答：答：若规定若规定若规定若规定花色为第一花色为第一花色为第一花色为第一关键字（高位），关键字（高位），关键字（高位），关键字（高位），面值为第二面值为第二面值为第二面值为第二关键字关键字关键字关键字（低位

19、），则使用（低位），则使用（低位），则使用（低位），则使用MSDMSD和和和和LSDLSD方法都可以达到排序目的。方法都可以达到排序目的。方法都可以达到排序目的。方法都可以达到排序目的。MSDMSD方法的思路：方法的思路：方法的思路：方法的思路：先设立先设立先设立先设立4 4个花色个花色个花色个花色“箱箱箱箱”，将全部牌按花色分，将全部牌按花色分，将全部牌按花色分，将全部牌按花色分别归入别归入别归入别归入4 4个箱内（每个箱中有个箱内（每个箱中有个箱内（每个箱中有个箱内（每个箱中有1313张牌）；然后对每个箱中的牌张牌）；然后对每个箱中的牌张牌）；然后对每个箱中的牌张牌）；然后对每个箱中的牌按

20、面值进行插入排序（或其它稳定算法）。按面值进行插入排序（或其它稳定算法）。按面值进行插入排序（或其它稳定算法）。按面值进行插入排序（或其它稳定算法）。LSDLSD方法的思路：方法的思路：方法的思路：方法的思路：先按面值分成先按面值分成先按面值分成先按面值分成1313堆（每堆堆（每堆堆（每堆堆（每堆4 4张牌），然后对张牌），然后对张牌），然后对张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。每堆中的牌按花色进行排序（用插入排序等稳定的算法）。每堆中的牌按花色进行排序（用插入排序等稳定的算法）。每堆中的牌按花色进行排序（用插入排序等稳定的算法）。想一想：用哪种方法更快些想一想：

21、用哪种方法更快些？最低位优先法最低位优先法最低位优先法最低位优先法LSD(Least Significant Digit first)LSD(Least Significant Digit first)492.2.单逻辑单逻辑单逻辑单逻辑关键字怎样关键字怎样关键字怎样关键字怎样“按位值按位值按位值按位值”排序？排序？排序？排序？设设设设n n n n 个记录的序列为：个记录的序列为：个记录的序列为：个记录的序列为：V0,V1,Vn-1 V0,V1,Vn-1 V0,V1,Vn-1 V0,V1,Vn-1，可以把每可以把每可以把每可以把每个记录个记录个记录个记录Vi Vi Vi Vi 的单关键码的单

22、关键码的单关键码的单关键码 KiKiKiKi 看成是一个看成是一个看成是一个看成是一个d d d d元组（元组（元组（元组（Ki1,Ki2,Ki1,Ki2,Ki1,Ki2,Ki1,Ki2,Kid,Kid,Kid,Kid），），），），则其中的每一个分量则其中的每一个分量则其中的每一个分量则其中的每一个分量KijKijKijKij(1(1(1(1 j j j j d)d)d)d)也也也也可看成是一个关键字。可看成是一个关键字。可看成是一个关键字。可看成是一个关键字。4 4注注注注1 1 1 1：K K K Ki i i i1 1 1 1最高位最高位最高位最高位，K K K Ki i i id d

23、 d d最低位；最低位；最低位；最低位；K K K Ki i i i共有共有共有共有d d d d位，可看成位，可看成位，可看成位，可看成d d d d元组；元组；元组；元组；注注注注2 2：每个分量每个分量每个分量每个分量K K K Ki i i ij j j j (1(1 j j d d)有有有有radixradix种取值，则称种取值，则称种取值，则称种取值，则称radixradix为为为为基数基数基数基数。2626(9,8,4)(9,8,4)(0,1,9)(0,1,9)（a,b,za,b,z）(d,i,a,n)(d,i,a,n)3 31010例例例例1 1：关键码关键码关键码关键码984

24、984可以看成是可以看成是可以看成是可以看成是 元组；基数元组；基数元组；基数元组；基数radixradix 为为为为 。例例例例2 2：关键码关键码关键码关键码diandian可以看成是可以看成是可以看成是可以看成是 元组；基数元组；基数元组；基数元组；基数radixradix 为为为为 。思路：思路：思路：思路：50因为有分组，故此算法需递归实现。讨论：讨论：讨论：讨论：是借用是借用MSDMSD方式来排序呢，还是借用方式来排序呢，还是借用LSDLSD方式？方式？例：例：初始关键字序列初始关键字序列T=（32,13,27,32*,19，33），），请分别请分别用用MSD和和LSD进行排序，并

25、讨论其优缺点。进行排序，并讨论其优缺点。法法1（MSD）：）：原始序列：原始序列：32,13,27,32*,19，33 先按高位先按高位K K K Ki i i i1 1 1 1 排序：排序：（13,19）,27,（32,32*，33）再按低位再按低位K K K Ki i i i2 2 2 2 排序排序：13,19，27,32,32*,33法法2（LSD）：）：原始序列：原始序列：32,13,27,32*,19，33 先按低位先按低位K K K Ki i i i2 2 2 2排序：排序：32,32*,13,33,27,19 再按高位再按高位K K K Ki i i i1 1 1 1排序：排序：

26、13,19,27,32,32*,33无需分组，易编程实现！51例例例例：T=T=（0202，7777，7070，5454，6464，2121，5555，1111），用），用），用），用LSDLSD排序。排序。排序。排序。分析：分析：分析：分析：各关键字可视为各关键字可视为各关键字可视为各关键字可视为2 2元组元组元组元组；每位的取值范围是：每位的取值范围是：每位的取值范围是：每位的取值范围是：0-90-9；即；即；即；即基数基数基数基数radixradix 10 10。因此，特设置因此，特设置因此，特设置因此，特设置1010个队列，并编号为个队列，并编号为个队列，并编号为个队列，并编号为0-9

27、0-9。1155216454707702原始序列原始序列原始序列原始序列1 12 23 34 45 56 67 78 8先对低位扫描先对低位扫描先对低位扫描先对低位扫描出队出队出队出队0 01 12 23 34 45 56 67 78 89 91010个队列个队列个队列个队列计算机怎样实现计算机怎样实现计算机怎样实现计算机怎样实现LSDLSD算法？算法？算法？算法？分配分配分配分配过程过程过程过程收集收集收集收集过程过程过程过程下一步下一步下一步下一步77556454021121701 12 23 34 45 56 67 78 8出队后序列出队后序列出队后序列出队后序列775554，6421，

28、117002又称散列过程！又称散列过程！520 01 12 23 34 45 56 67 78 89 9再次入队再次入队再次入队再次入队再次出队再次出队再次出队再次出队再对高位扫描再对高位扫描再对高位扫描再对高位扫描小结：小结：小结：小结：排序时经过了反复的排序时经过了反复的“分配分配”和和“收集收集”过程。当对关过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序键字所有的位进行扫描排序后，整个序列便从无序变为有序了。了。77556454021121701 12 23 34 45 56 67 78 8出队后序列出队后序列出队后序列出队后序列70，776454，55211102再次

29、再次再次再次分配分配分配分配再次再次再次再次收集收集收集收集7770645554211102再次出队后序列再次出队后序列再次出队后序列再次出队后序列这种这种这种这种LSDLSDLSDLSD排序方法称为：排序方法称为：排序方法称为：排序方法称为：基数排序基数排序基数排序基数排序53 请实现以下关键字序列的请实现以下关键字序列的请实现以下关键字序列的请实现以下关键字序列的链式基数排序链式基数排序链式基数排序链式基数排序：T=T=T=T=（614614614614，738738738738，921921921921，485485485485，637637637637，101101101101，215

30、215215215，530530530530，790790790790，306306306306）例例例例:614614921921485485637637738738101101215215530530790790306306第一趟分配第一趟分配第一趟分配第一趟分配e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9原始序列链表：原始序列链表：原始序列链表：原始序列链表：r0（从最低位（从最低位（从最低位（从最低位 i i=3=3开始排序，开始排序，开始排序，开始排序，

31、f 是队首指针，是队首指针，是队首指针，是队首指针，e 为队尾指针）为队尾指针）为队尾指针）为队尾指针）第一趟收集第一趟收集第一趟收集第一趟收集（让队尾指针（让队尾指针（让队尾指针（让队尾指针ei 链接到下一非空队首指针链接到下一非空队首指针链接到下一非空队首指针链接到下一非空队首指针fi+1 即可）即可）即可）即可）530790921101614485215306637738r054第一趟收集的结果：第一趟收集的结果：第一趟收集的结果：第一趟收集的结果：e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3

32、 f4 f5 f6 f7 f8 f9第二趟分配第二趟分配第二趟分配第二趟分配（按次低位（按次低位（按次低位（按次低位 i i=2 =2）530790921101614485215306637738第二趟收集第二趟收集第二趟收集第二趟收集（让队尾指针（让队尾指针（让队尾指针（让队尾指针ei 链接到下一非空队首指针链接到下一非空队首指针链接到下一非空队首指针链接到下一非空队首指针fi+1 ）530790921101614485215306637738r0r055第二趟收集的结果：第二趟收集的结果：第二趟收集的结果：第二趟收集的结果：530790921101614485215306637738e0

33、e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第三趟分配第三趟分配第三趟分配第三趟分配（按最高位（按最高位（按最高位（按最高位 i i=1 =1）第三趟收集第三趟收集第三趟收集第三趟收集（让队尾指针（让队尾指针（让队尾指针（让队尾指针ei 链接到下一非空队首指针链接到下一非空队首指针链接到下一非空队首指针链接到下一非空队首指针fi+1 ）530790921101614485215306637738r0r0排序结束！排序结束！排序结束！排序结束！56基数排序算法分析基数排序

34、算法分析 假假假假设设设设有有有有n n 个个个个记记记记录录录录,每每每每个个个个记记记记录录录录的的的的关关关关键键键键字字字字有有有有d d 位位位位，每每每每个个个个关关关关键键键键字字字字的的的的取取取取值值值值有有有有radixradix个个个个,则则则则需需需需要要要要radixradix个个个个队队队队列列列列,进进进进行行行行d d 趟趟趟趟“分分分分配配配配”与与与与“收集收集收集收集”。因此时间复杂度：。因此时间复杂度：。因此时间复杂度：。因此时间复杂度：O(d(n+radix)O(d(n+radix)。基数排序需要增加基数排序需要增加基数排序需要增加基数排序需要增加n+

35、2radixn+2radix个附加链接指针，空间效率低个附加链接指针，空间效率低个附加链接指针，空间效率低个附加链接指针，空间效率低 空间复杂度：空间复杂度：空间复杂度：空间复杂度：OO（radixradix）.稳定性：稳定。稳定性：稳定。稳定性：稳定。稳定性：稳定。(一直前后有序一直前后有序一直前后有序一直前后有序)。用用用用途途途途：若若若若基基基基数数数数radixradix相相相相同同同同，对对对对于于于于记记记记录录录录个个个个数数数数较较较较多多多多而而而而关关关关键键键键码码码码位位位位数数数数较少的情况，使用链式基数排序较好。较少的情况，使用链式基数排序较好。较少的情况，使用链

36、式基数排序较好。较少的情况，使用链式基数排序较好。特点：特点：特点：特点：不用比较和移动，改用分配和收集，时间效率高！不用比较和移动，改用分配和收集，时间效率高！不用比较和移动，改用分配和收集，时间效率高！不用比较和移动，改用分配和收集，时间效率高！57各种内部排序方法的比较各种内部排序方法的比较 (教材教材P289）排序方法排序方法排序方法排序方法 最好情况最好情况最好情况最好情况 平均时间平均时间平均时间平均时间 最坏情况最坏情况最坏情况最坏情况辅助存储辅助存储辅助存储辅助存储稳定性稳定性稳定性稳定性 简单排序简单排序 O(n)O(n2)O(n2)O(1）稳定稳定 快速排序快速排序O(nl

37、gn)O(nlgn)O(n2)O(lgn)不稳定不稳定 堆排序堆排序 O(nlgn)O(nlgn)O(nlgn)O(1）不稳定不稳定 归并排序归并排序 O(nlgn)O(nlgn)O(nlgn)O(n）稳定稳定基数排序基数排序O(d(n+rd)O(d(n+rd)O(d(n+rd)O(rd)稳定稳定 简单选择简单选择 O(n2)O(n2)O(n2)O(1）不稳定不稳定 直接插入直接插入 O(n)O(n2)O(n2)O(1）稳定稳定 折半插入折半插入O(nlgn)O(nlgn)O(nlgn)O(1）稳定稳定冒泡冒泡 O(n)O(n2)O(n2)O(1）稳定稳定 58讨论：讨论：若初始记录基本无序，则选用哪些排序方法比较适若初始记录基本无序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？合？若初始记录基本无序，则最好选用哪些排序方法？答：答：对基本有序的情况，可选用堆排序、冒泡排序、归并排对基本有序的情况，可选用堆排序、冒泡排序、归并排序等方法；序等方法；在基本无序的情况下，最好选用快速排序、希尔排序。在基本无序的情况下，最好选用快速排序、希尔排序。想一想：想一想：能选用折半排序么？能选用折半排序么？59