数据结构课件10讲义..ppt

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

1、第十章第十章 排序排序精英专升本精英专升本10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较1 1、什么是排序？、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。例如：例如：例如：例如：将下列关键字序列将下列关键字序列将下列关键字序列将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97

2、10.1 概概 述述2 2、内部排序和外部排序、内部排序和外部排序若整个排序过程不需要访问外存不需要访问外存便能完成，则称此类排序问题为内部排内部排序序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序外部排序。3 3、内部排序的方法、内部排序的方法内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区时间效率时间效率时间效率时间效率排序速度（排序速度（排序速度（排序速度（比较次数比较次数比较次数比较次数与与与与移动次数移动次数移动次数移动次数）空

3、间效率空间效率空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小占内存辅助空间的大小占内存辅助空间的大小稳稳稳稳定定定定性性性性A A A A和和和和B B B B的的的的关关关关键键键键字字字字相相相相等等等等，排排排排序序序序后后后后A A A A、B B B B的的的的先先先先后后后后次次次次序保持不变，则称这种排序算法是稳定的序保持不变，则称这种排序算法是稳定的序保持不变，则称这种排序算法是稳定的序保持不变，则称这种排序算法是稳定的。4.4.排序算法的好坏如何衡量？排序算法的好坏如何衡量？例如：例如：例如：例如：将下列关键字序列将下列关键字序列将下列关键字序列将下列关键字序列52

4、,49,97*,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,97*,97排序算法分类排序算法分类规则不同规则不同插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序时间复杂度不同时间复杂度不同简单排序简单排序O(nO(n2 2)先进排序先进排序O(nlogO(nlog2 2n n)10.2 10.2 插入排序插入排序基本思想：基本思想：基本思想：基本思想：每步将一个待排序的对象，按其关键码大小，每步将一个待排序的对象，按其关键码大小，插入插入到前面到前面已经排好序的一组对象已经排好序的一组对象的的适当位置适当位置上上，直到对，直到对

5、象全部插入为止。象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的即边插入边排序，保证子序列中随时都是排好序的即边插入边排序，保证子序列中随时都是排好序的即边插入边排序，保证子序列中随时都是排好序的直接插入排序直接插入排序直接插入排序直接插入排序;折半插入排序折半插入排序折半插入排序折半插入排序;希尔排序希尔排序希尔排序希尔排序有序序列R1.i-1Ri无序序列Ri.n一趟一趟直接插入排序的基本思想：有序序列R1.i无序序列Ri+1.n直接插入排序直接插入排序利用“顺序查找顺序查找”实现“在R1.i-1中查找查找Ri的插入位置”直接插入排序直接插入排序排序过程：整个排序过程为排序过程：

6、整个排序过程为n-1n-1趟插入，即先将序列中趟插入，即先将序列中第第1 1个记个记录录看成是一个有序子序列，然后从看成是一个有序子序列，然后从第第2 2个记录个记录开始，开始，逐个逐个进行插进行插入，直至整个序列有序入，直至整个序列有序。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】例例例例（1313131

7、3，6 6 6 6，3 3 3 3，31313131，9 9 9 9，27272727，5 5 5 5，11111111）21212525494925*25*161608080 1 2 3 4 5 6暂暂存存2121i i=2=2i i=3=3i i=5=5i i=4=4i i=6=625252549494925*2525494925*25*494916161625*25*080808494921212525494925*25*2121初态：初态：1616494925*25*2525212116160808完成!将序列存入顺序表将序列存入顺序表L L中，将中，将L.r0L.r0作为哨兵作为哨兵

8、（2121，2525，4949，2525*，1616，0808）*表示后一个表示后一个2525从Ri-1起向前进行顺序查找，监视哨设置在监视哨设置在R0；R0=Ri;/设置“哨兵”循环结束表明Ri的插入位置为j+1R0jRifor(j=i-1;R0.keyRj.key;-j);/从后往前找j=i-1插入位置插入位置对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R0.keyRj.key;-j);Rj+1=RjR0jRij=i-1上述循环结束后可以直接进行上述循环结束后可以直接进行“插入插入”插入位置插入位置令i=2，3，,n,实现整

9、个序列的排序。for(i=2;i=n;+i)if(Ri.keyRi-1.key)在在 R1.i-1中查找中查找Ri的插入位置的插入位置;插入插入Ri;voidInsertionSort(SqList&L)/对顺序表L作直接插入排序。for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)/InsertSortL.r0=L.ri;/复制为监视哨for(j=i-1;L.r0.keyL.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置内部排序的时间分析：内部排序的时间分析：实现内部排序的基本操作基本操作有两个：（2）“移动

10、移动”记录。（1）“比较比较”序列中两个关键字的大小；算法分析算法分析设对象个数为设对象个数为设对象个数为设对象个数为n n，则执行，则执行，则执行，则执行n-1趟趟趟趟比较次数比较次数和和和和移动次数移动次数与初始排列有关与初始排列有关与初始排列有关与初始排列有关最好情况下：最好情况下：每趟只需比较每趟只需比较 1 次，不移动次，不移动 总比较次数为总比较次数为 n-121212525494925*25*16160808for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)最坏情况下：第最坏情况下：第 i i 趟比较趟比较i i次，移动次，移动i+1i+1次

11、次21212525494925*25*16160808算法分析算法分析比较次数比较次数移动次数移动次数if(L.ri.keyL.ri-1.key)L.r0=L.ri;/复制为哨兵复制为哨兵 L.rj+1=L.r0;/插入到正确位置插入到正确位置 若出现各种可能排列的概率相同，则可取最好情况若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况和最坏情况的平均情况平均情况平均情况比较次数比较次数和和移动次数移动次数为为n n2 2/4/4时间复杂度为时间复杂度为 o(o(n n2 2)空间复杂度为空间复杂度为 o(1)是一种是一种稳定稳定的排序方法的排序方法21212525494925

12、*25*1616080821212525494925*25*161608080 1 2 3 4 5算法分析算法分析因为R1.i-1是一个按关键字有序的有序序列，则可以利用折半查找折半查找实现“在R1.i-1中查找查找Ri的插入位置”，如此实现的插入排序为折半插折半插入入排序。二、折半插入排序二、折半插入排序i=2折半插入排序折半插入排序i=3折半插入排序折半插入排序i=4折半插入排序折半插入排序i=5折半插入排序折半插入排序i=6折半插入排序折半插入排序voidBiInsertionSort(SqList&L)/BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置

13、；for(i=2;i=high+1;-j)L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入low=1;high=i-1;while(low=high)m=(low+high)/2;/折半if(L.r0.key 0)&(flag=1)flag=0;for(j=1;jL.rj+1.key)flag=1;x=L.rj;L.rj=L.rj+1;L.rj+1=x;最好情况下：最好情况下：21212525494925*25*16160808算法分析算法分析时间复杂度为时间复杂度为 o(o(n n2 2)空间复杂度为空间复杂度为 o(1)是一种是一种稳定稳定的排序方法的排序方法需需 n

14、-1趟排序，趟排序，第第i趟比较趟比较n-i次，移动次，移动3(n-i)次次最坏情况下：最坏情况下：快速排序快速排序基本思想：基本思想：任取一个元素任取一个元素 (如第一个如第一个)为中心为中心所有比它所有比它小小的元素一律前放，比它的元素一律前放，比它大大的元素一律的元素一律后放，形成后放，形成左右两个子表左右两个子表；对各子表重新选择对各子表重新选择中心中心元素并依此规则调整，直元素并依此规则调整，直到每个子表的元素到每个子表的元素只剩一个只剩一个一趟快速排序（一次划分）一趟快速排序（一次划分）目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移

15、动至该记录之前移动至该记录之前，反之，凡关键字大于枢轴关键字大于枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分分割成两部分：Rs.i-1和Ri+1.t，且Rj.keyRi.keyRj.key (sji-1)枢轴枢轴(i+1jt)。stlowhigh设设 Rs=52 为枢轴为枢轴将Rhigh.key和枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字将Rlow.key和枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow可见，经

16、过“一次划分一次划分”，将关键字序列 52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75intPartition(RedTypeR,intlow,inthigh)/PartitionR0=Rlow;pivotkey=Rlow.key;/枢轴while(lowhigh)while(low=pivotkey)-high;/从右向左搜索Rlow=Rhigh;while(lowhigh&Rlow.key=pivotkey)+low;/从左向右搜索Rhigh=Rlow;Rlow=R0;returnlow;三、快速排序三、快速排序

17、首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序voidQSort(RedType&R,ints,intt)/对记录序列Rs.t进行快速排序if(st-1)/长度大于1/QSortpivotloc=Partition(R,s,t);/对Rs.t进行一次划分一次划分QSort(R,s,pivotloc-1);/对低子序列递归排序，pivotloc是枢轴位置是枢轴位置QSort(R,pivotloc+1,t);/对高子序列递归排序voidQuickS

18、ort(SqList&L)/对顺序表进行快速排序QSort(L.r,1,L.length);/QuickSort第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。可以证明，平均计算时间是可以证明，平均计算时间是O(nlog2n)。实验结果表明：就实验结果表明：就平均计算时间平均计算时间而言，快速排序是我而言，快速排序是我们所讨论的所有内排序方法中们所讨论的所有内排序方法中最好最好的一个的一个。快速排序是递归的，需要有一个栈存放每层递归调用快速排序是递归的，需要有一个栈存放每层递归调用时参数时参数（新的（新的lowlow和和highhigh）。最大递归调用层次数与递

19、归树的深度一致，因此，要最大递归调用层次数与递归树的深度一致，因此，要求存储开销为求存储开销为 O(log2n)。算法分析算法分析算法分析算法分析最好：划分后，左侧右侧子序列的最好：划分后，左侧右侧子序列的长度相同长度相同最最坏坏：从从小小到到大大排排好好序序，递递归归树树成成为为单单支支树树，每每次次划划分分只只得得到到一一个个比比上上一一次次少少一一个个对对象象的的子子序序列列，必必须须经经过过 n n-1-1 趟趟才才能能把把所所有有对对象象定定位位，而而且且第第 i i 趟趟需需要要经经过过 n n-i i 次次关关键键码码比比较较才才能能找找到到第第 i i 个个对对象象的的安安放放

20、位置位置算法分析算法分析时间效率：时间效率：O(nlog2n)每趟确定的元素呈指数增加每趟确定的元素呈指数增加空间效率：空间效率：O（log2n）递归要用到栈空间递归要用到栈空间稳稳 定定 性：性：不稳定不稳定 可选任一元素为支点。可选任一元素为支点。10.4 10.4 选择排序选择排序基本思想：基本思想：每一趟在后面每一趟在后面 n-i+1个中选出关键码最小的对象个中选出关键码最小的对象,作作为有序序列的第为有序序列的第 i 个记录个记录简简 单单 选选 择择 排排 序序堆堆 排排 序序一、简单选择排序一、简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列Ri.n

21、第i趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列Ri+1.n212125*25*i=1=12525161649490808最小者最小者 0808交换交换交换交换21,0821,0825251616080825*25*49492121i=2=2最小者最小者 1616交换交换交换交换25,1625,164949i=3=30808161625*25*25252121最小者最小者 2121交换交换交换交换49,2149,21简单选择排序简单选择排序494925*25*0 1 2 3 4 5i=4=40808161625252121最小者最小者 25*25*无交换无交换无交换无交换25

22、*25*i=5=54949最小者最小者 2525无交换无交换无交换无交换252521211616080825251616080825*25*49492121结果结果各趟排序后的结果各趟排序后的结果简单选择排序简单选择排序简单选择排序的算法描述如下：voidSelectSort(ElemR,intn)/对记录序列R1.n作简单选择排序。for(i=1;i0;-i)HeapAdjust(H.r,i,H.length);/建大顶堆for(i=H.length;i1;-i)H.r1H.ri;/将堆顶记录和当前未经排序子序列/H.r1.i中最后一个记录相互交换HeapAdjust(H.r,1,i-1);

23、/对H.r1进行筛选如何如何“建堆建堆”？两个问题两个问题:如何如何“调整调整”？定义堆类型为定义堆类型为:typedef SqListHeapType;/堆采用顺序表表示之 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 8407012101 1、如何将无序序列建成堆、如何将无序序列建成堆思考：有思考：有n 个结点的完全二叉树采用顺序个结点的完全二叉树采用顺序存储，最后一个分支结点的标号是多少？存储，最后一个分支结点的标号是多少？n/2n/2 从第从第 n/2 个元素起，至第一个元素止，进行反复个元素起，至第一个元素止，进行反复筛选筛选堆

24、堆 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210 30 1 60 240 4 70 510 7 1 2 3 4 5 6 7 3060 840701210无序序列建成堆无序序列建成堆1 8 12 3 6 30 1 60 240 4 70 5 12 810 7 1 2 3 4 5 6 7 3060124070810无序序列建成堆无序序列建成堆1 3 6 30 1 6040 4 12 810 7 1 2 3 4 5 6 7 3060124070810无序序列建成堆无序序列建成堆2 3 6 2 70 5 30 1 7040 4

25、 12 810 7 1 2 3 4 5 6 7 3070124060810无序序列建成堆无序序列建成堆2 3 6 2 60 5 7040 4 12 810 7 1 2 3 4 5 6 7 3070124060810无序序列建成堆无序序列建成堆3 3 6 2 60 5 30 1 3040 4 12 810 7 1 2 3 4 5 6 7 7030124060810无序序列建成堆无序序列建成堆3 3 6 2 60 5 70 1 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810无序序列建成堆无序序列建成堆3 3 6 2 5 70 1 30建堆完毕建堆完毕将根结点

26、将根结点r1与左、右子树根结点比较，并与左、右子树根结点比较，并与小者与小者交换交换重复重复直至叶子结点，得到新的堆直至叶子结点，得到新的堆交换交换r1和和rn后，如何将后，如何将r1.n-1重新调整，重新调整，使之成使之成为新堆？为新堆？筛筛筛筛选选选选2 2、堆的重新调整、堆的重新调整 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810 3 6 2 30 5 70 1堆的重新调整堆的重新调整1堆的重新调整堆的重新调整1 6040 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 510 1706012403081070701060106

27、010104040堆的重新调整堆的重新调整2 4010 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 560 160401210308107070堆的重新调整堆的重新调整2 4010 4 12 6010 7 1 2 3 4 5 6 7 3 6 2 30 58 1840121030601070706060堆的重新调整堆的重新调整2 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 1403012108601070706060堆的重新调整堆的重新调整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 140

28、3012108601070706060堆的重新调整堆的重新调整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 1830121086010707060604040堆的重新调整堆的重新调整3 108 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新调整堆的重新调整4 108 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新调整堆的重新调整4 1030 4 12 6010 7 1 2 3 4 5

29、6 7 3 6 28 58 18101230860107070606040403030堆的重新调整堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 512 11210830860107070606040403030堆的重新调整堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新调整堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆

30、的重新调整堆的重新调整5 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新调整堆的重新调整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新调整堆的重新调整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18883086010707060604040303012121010算法分析算法分析时间效率：时间效率：O(nlogO(nlog2 2n)n)空间效率

31、：空间效率：O O（1 1）稳稳 定定 性：性：不稳定不稳定适用于适用于n 较大较大的情况的情况已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法堆排序方法堆排序方法堆排序方法建小根堆，请画出建堆的过程。练习：练习：10.5 10.5 归并排序归并排序归并：将两个或两个以上的有序表组合成一个新有序表归并：将两个或两个以上的有序表组合成一个新有序表2-2-路归并排序路归并排序排序过程排序过程初始序列看成初始序列看成n个个有序子序列，每个子序列长度为有序子序列，每个子序列长度为1两两合并两两合并，得到，得到 n/2 个长度为个长度为2或或1的

32、有序子序列的有序子序列再两两合并，重复直至得到再两两合并，重复直至得到一个一个长度为长度为n的有序序的有序序列为止列为止将两个将两个顺序表合并成一个有序表顺序表合并成一个有序表0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7130 1 2 3 44913659776780AB0 1 2 3

33、 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0

34、 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680B B 表的元素都表的元素都已移入已移入 C C 表，表，只需将只需将 A A 表的表的剩余部分移入剩余部分移入 C C 表即可表即可0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965768097例例初始关键字：初始关键字：49 38 65 97 76 13 27一趟

35、归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 49 65 76 97算法分析算法分析时间效率：时间效率：O(nlogO(nlog2 2n)n)空间效率：空间效率：O O（n n）稳稳 定定 性：性：稳定稳定 以扑克牌排序为例。每张扑克牌有两个以扑克牌排序为例。每张扑克牌有两个以扑克牌排序为例。每张扑克牌有两个以扑克牌排序为例。每张扑克牌有两个“排序码排序码排序码排序码”：花色花色花色花色和和和和面值面值面值面值。其有序关系为：。其有序关系为：。其有序关系为：。其有序关系为：u

36、u 花色：花色：花色：花色：uu 面面面面值值值值：2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10101010 J J J J Q Q Q Q K K K K A A A A 可以把所有扑克牌排成以下次序：可以把所有扑克牌排成以下次序：可以把所有扑克牌排成以下次序：可以把所有扑克牌排成以下次序：2,2,2,2,A,A,A,A,2,2,2,2,A,A,A,A,2,2,2,2,A,A,A,A,2,2,2,2,A A A A 花色相同的情况下，比较面值。花色相同的情况下，比较面值。花色相同的情况下，比较面值。花色相

37、同的情况下，比较面值。10.6 10.6 基数排序基数排序前面的排序方法主要通过关键字值之间的比较和移动前面的排序方法主要通过关键字值之间的比较和移动前面的排序方法主要通过关键字值之间的比较和移动前面的排序方法主要通过关键字值之间的比较和移动而基数排序不需要关键字之间的比较而基数排序不需要关键字之间的比较而基数排序不需要关键字之间的比较而基数排序不需要关键字之间的比较对对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序：22 33 AA 22 33 AA 22 33 AA 22 33 A A两个关键字：花色（两个关键字：花色（）面值（面值（2323AA）并且并且“花色花色”地位高于地位高

38、于“面值面值”多关键字排序多关键字排序链式基数排序链式基数排序uu最高位优先最高位优先最高位优先最高位优先MSD MSD MSD MSD(Most Significant Digit first Most Significant Digit first Most Significant Digit first Most Significant Digit first)uu最低位优先最低位优先最低位优先最低位优先LSDLSDLSDLSD(Least Significant Digit Least Significant Digit Least Significant Digit Least Si

39、gnificant Digit firstfirstfirstfirst)链式基数排序：用链式基数排序：用链表链表链表链表作存储结构的基数排序作存储结构的基数排序先对先对最高位最高位关键字关键字k1k1（如花色）排序，将序列分如花色）排序，将序列分成若干子序列，每个子序列有相同的成若干子序列，每个子序列有相同的k1k1值；值；然后让每个子序列对然后让每个子序列对次关键字次关键字k2k2（如面值）排序，如面值）排序，又分成若干更小的子序列；又分成若干更小的子序列；依次重复，直至就每个子序列对依次重复，直至就每个子序列对最低位关键字最低位关键字kdkd排序排序，就可以得到一个有序的序列。，就可以得

40、到一个有序的序列。最高位优先法最高位优先法十进制数比较可以看作是一个多关键字排序十进制数比较可以看作是一个多关键字排序十进制数比较可以看作是一个多关键字排序十进制数比较可以看作是一个多关键字排序最高位优先法最高位优先法十位十位首先依据首先依据首先依据首先依据最低位最低位最低位最低位排序码排序码排序码排序码KdKdKdKd对所有对象进行一趟排序对所有对象进行一趟排序对所有对象进行一趟排序对所有对象进行一趟排序再依据再依据再依据再依据次低位次低位次低位次低位排序码排序码排序码排序码Kd-1Kd-1Kd-1Kd-1对上一趟排序结果排序对上一趟排序结果排序对上一趟排序结果排序对上一趟排序结果排序依次重

41、复，直到依据依次重复，直到依据依次重复，直到依据依次重复，直到依据排序码排序码排序码排序码K1K1K1K1最后一趟排序最后一趟排序最后一趟排序最后一趟排序完成，就完成，就完成，就完成，就可以得到一个有序的序列。可以得到一个有序的序列。可以得到一个有序的序列。可以得到一个有序的序列。最低位优先法最低位优先法这种方法这种方法这种方法这种方法不需要再分组不需要再分组不需要再分组不需要再分组，而是整个对象组都参加排序，而是整个对象组都参加排序，而是整个对象组都参加排序，而是整个对象组都参加排序最低位优先法最低位优先法先决条件：先决条件：先决条件：先决条件：知道各级关键字的知道各级关键字的主次关系主次关

42、系知道各级关键字的知道各级关键字的取值范围取值范围链式基数排序链式基数排序利用利用“分配分配”和和“收集收集”对关键字进行排序对关键字进行排序过程过程过程过程首先对首先对低位关键字低位关键字排序，各个记录按照此位关键字排序，各个记录按照此位关键字的值的值分配分配到相应的序列里。到相应的序列里。按照序列对应的值的大小，从各个序列中将记录按照序列对应的值的大小，从各个序列中将记录收集收集，收集后的序列按照此位关键字有序。，收集后的序列按照此位关键字有序。在此基础上，对前一位关键字进行排序。在此基础上，对前一位关键字进行排序。初始状态：初始状态：278109063930589184505269008

43、083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集一趟收集00806308310918426927850

44、5589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集二趟收集设置设置1010个队列个队列，fifi和和eiei分别头指针和尾指针分别头指针和尾指针第一趟分配第一趟分配第一趟分配第一趟分配对最低位关键字（个位）进行，改变记对最低位关键字（个位）进行，改变记录的指针值，录的指针值，将链表中记录分配至将链表中记录分配至1010个链队列中个链队列中，每个队列记录的关键字的个位相同每个队列记录的关键字

45、的个位相同第一趟收集第一趟收集第一趟收集第一趟收集是改变所有非空队列的是改变所有非空队列的队尾记录的指针队尾记录的指针队尾记录的指针队尾记录的指针域，令其指向域，令其指向下一个非空队列的队头记录下一个非空队列的队头记录下一个非空队列的队头记录下一个非空队列的队头记录，重新将重新将1010个队列链成一个链表个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，重复上述两步，进行第二趟、第三趟分配和收集，分别对分别对十位、百位十位、百位进行，最后得到一个有序序列进行，最后得到一个有序序列链式基数排序步骤链式基数排序步骤n n重复执行重复执行重复执行重复执行d d d d趟趟趟趟“分配分配分

46、配分配”与与与与“收集收集收集收集”n n每每每每趟趟趟趟对对对对 n n n n 个个个个记记记记录录录录进进进进行行行行“分分分分配配配配”，对对对对rdrdrdrd个个个个队队队队列列列列进进进进行行行行“收收收收集集集集”n n需要增加需要增加需要增加需要增加n+2rdn+2rdn+2rdn+2rd个附加链接指针。个附加链接指针。个附加链接指针。个附加链接指针。n n个记录个记录个记录个记录每个记录有每个记录有每个记录有每个记录有 d d 位关键字位关键字位关键字位关键字关键字关键字关键字关键字取值范围取值范围取值范围取值范围rdrd(如十进制为如十进制为如十进制为如十进制为10)10

47、)算法分析算法分析时间效率：时间效率：O(O(d(n+rd)d(n+rd)空间效率：空间效率：O(O(n+rd)n+rd)稳稳 定定 性：性：稳定稳定（数据不是（数据不是顺次后移顺次后移时将导致方法不稳定）时将导致方法不稳定）排序算法比较排序算法比较记忆口诀：（1）平均时间复杂度：以O（nlog2n）的速度快快快快希希希希归堆归堆归堆归堆（看看这句话包括哪些排序），但是太快（快速排序）也不好，最坏达到O（n2）冒泡冒的好是O（n），冒得不好就是O（n2）直接插入插得好，就是O（n），直接插入插得不好就是O（n2）（2）空间复杂度：记住特殊的三个：快速排序：快速排序：快速排序：快速排序：O(lo

48、gn)O(logn)；归并排序：O(n)基数排序：O（dr）剩下的都是O(1)（3）稳定性：一句话解决，快希选一堆（玩具来玩）快希选一堆（玩具来玩）快希选一堆（玩具来玩）快希选一堆（玩具来玩）其中包括快速排序、希尔排序、简单选择排序、堆排序！其他的全是稳定的按平均时间排序方法分为四类：按平均时间排序方法分为四类：O(nO(n2 2)、O(nlogO(nlogn n)、O(nO(n1+1+)快速排序快速排序是基于比较的内部排序中平均性能最好的是基于比较的内部排序中平均性能最好的排序算法比较排序算法比较为避免顺序存储时大量移动记录的时间开销，可考为避免顺序存储时大量移动记录的时间开销，可考虑用虑用

49、链表作为存储结构链表作为存储结构直接插入排序、归并排序直接插入排序、归并排序不宜采用不宜采用链表作为存储结构的链表作为存储结构的折半插入排序、希尔排序、快速排序、堆排序折半插入排序、希尔排序、快速排序、堆排序排序算法比较排序算法比较（1 1）分布随机，稳定性不做要求，则采用）分布随机，稳定性不做要求，则采用快速快速排序排序（2 2）内存允许，要求排序稳定时，则采用）内存允许，要求排序稳定时，则采用归并归并排序排序（3 3）可可能能会会出出现现正正序序或或逆逆序序，稳稳定定性性不不做做要要求求，则则采采用用堆堆排序或排序或归并归并排序排序排序算法选择规则排序算法选择规则n较大时较大时（1 1）基

50、本有序，要求稳定，则采用基本有序，要求稳定，则采用直接插入直接插入排序排序（2）分布随机，稳定性不做要求，则采用）分布随机，稳定性不做要求，则采用直接选择直接选择排排序，若排序码不接近逆序，也可以采用直接插入序，若排序码不接近逆序，也可以采用直接插入排序排序n较小时较小时排序的概念排序的概念 定义定义 稳定性稳定性常用的排序算法常用的排序算法直接插入排序、二分法插入排序、简单选择排序直接插入排序、二分法插入排序、简单选择排序冒泡排序、希尔排序、快速排序、堆排序冒泡排序、希尔排序、快速排序、堆排序归并排序、基数排序归并排序、基数排序各类内部排序方法的特点各类内部排序方法的特点时间复杂度、空间复杂