《数据结构课件10讲义.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构课件10讲义.优秀PPT.ppt（134页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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,9710.1 概概 述述2
2、2、内部排序和外部排序、内部排序和外部排序若整个排序过程不须要访问外存便能完成，则称此类排序问题为内部排序；反之，若参与排序的记录数量很大，整个序列的排序过程不行能在内存中完成，则称此类排序问题为外部排序。3 3、内部排序的方法、内部排序的方法内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区时间效率时间效率排序速度（比较次数与移动次数）排序速度（比较次数与移动次数）空间效率空间效率占内存协助空间的大小占内存协助空间的大小稳稳定定性性AA和和B B的的关关键键字字相相等等，排排序序后后A A
3、、B B的的先先后后次次序序保保持持不不变变，则则称称这这种种排排序序算算法法是是稳稳定定的。的。4.4.排序算法的好坏如何衡量？排序算法的好坏如何衡量？例如：例如：例如：例如：将下列关键字序列将下列关键字序列将下列关键字序列将下列关键字序列52,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
4、10.2 插入排序插入排序基本思想：基本思想：基本思想：基本思想：每步将一个待排序的对象，按其关键码大小，每步将一个待排序的对象，按其关键码大小，插入插入到前面到前面已经排好序的一组对象已经排好序的一组对象的的适当位置适当位置上上，直到对，直到对象全部插入为止。象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的即边插入边排序，保证子序列中随时都是排好序的即边插入边排序，保证子序列中随时都是排好序的即边插入边排序，保证子序列中随时都是排好序的干脆插入排序干脆插入排序干脆插入排序干脆插入排序;折半插入排序折半插入排序折半插入排序折半插入排序;希尔排序希尔排序希尔排序希尔排序有序序列R1.
5、i-1Ri无序序列Ri.n一趟干脆插入排序的基本思想：一趟干脆插入排序的基本思想：有序序列R1.i无序序列Ri+1.n干脆插入排序干脆插入排序利用“依次查找”实现“在R1.i-1中查找Ri的插入位置”干脆插入排序干脆插入排序排序过程：整个排序过程为排序过程：整个排序过程为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】
6、,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】例例例例（13131313，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*2
7、5*494916161625*25*080808494921212525494925*25*2121初态：初态：1616494925*25*2525212116160808完成!将序列存入依次表将序列存入依次表L L中，将中，将L.r0L.r0作为哨兵作为哨兵（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插入位置插入位置对于在查找过程中找到的那些关键字不小
8、于Ri.key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R0.keyRj.key;-j);Rj+1=RjR0jRij=i-1上述循环结束后可以干脆进行上述循环结束后可以干脆进行“插入插入”插入位置插入位置令i=2，3，,n,实现整个序列的排序。for(i=2;i=n;+i)if(Ri.keyRi-1.key)在在 R1.i-1中查找中查找Ri的插入位置的插入位置;插入插入Ri;void InsertionSort(SqList&L)/对依次表对依次表 L 作干脆插入排序。作干脆插入排序。for(i=2;i=L.length;+i)if(L.ri.key L.ri-1.key)
9、/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）“移动移动”记录。（1）“比较比较”序列中两个关键字的大小；算法分析算法分析设对象个数为设对象个数为设对象个数为设对象个数为n n，则执行，则执行，则执行，则执行n-1趟趟趟趟比较次数比较次数和和和和移动次数移动次数与初始排列有关与初始排列有关与初始排列有关与初始排列有关最好情况下：最好情况下：每趟只需比较每趟只需比较 1
10、次，不移动次，不移动 总比较次数为总比较次数为 n-121212525494925*25*16160808for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)最坏状况下：第最坏状况下：第 i i 趟比较趟比较i i次，移动次，移动i+1i+1次次21212525494925*25*16160808算法分析算法分析比较次数比较次数移动次数移动次数if(L.ri.keyL.ri-1.key)L.r0=L.ri;/复制为哨兵复制为哨兵 L.rj+1=L.r0;/插入到正确位置插入到正确位置 若出现各种可能排列的概率相同，则可取最好状况若出现各种可能排列的概率相同，
11、则可取最好状况和最坏状况的平均状况和最坏状况的平均状况平均状况比较次数和移动次数为平均状况比较次数和移动次数为n2/4n2/4时间困难度为时间困难度为 o(n2)o(n2)空间困难度为空间困难度为 o(1)o(1)是一种稳定的排序方法是一种稳定的排序方法21212525494925*25*1616080821212525494925*25*161608080 1 2 3 4 5算法分析算法分析因为R1.i-1是一个按关键字有序的有序序列，则可以利用折半查找折半查找实现“在R1.i-1中查找查找Ri的插入位置”，如此实现的插入排序为折半插折半插入入排序。二、折半插入排序二、折半插入排序i=2折半
12、插入排序折半插入排序i=3折半插入排序折半插入排序i=4折半插入排序折半插入排序i=5折半插入排序折半插入排序i=6折半插入排序折半插入排序voidBiInsertionSort(SqList&L)/BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；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=
13、1;x=L.rj;L.rj=L.rj+1;L.rj+1=x;最好状况下：最好状况下：21212525494925*25*16160808算法分析算法分析时间困难度为时间困难度为 o(n2)o(n2)空间困难度为空间困难度为 o(1)o(1)是一种稳定的排序方法是一种稳定的排序方法需需 n-1趟排序，趟排序，第第i趟比较趟比较n-i次，移动次，移动3(n-i)次次最坏状况下：最坏状况下：快速排序快速排序基本思想：基本思想：任取一个元素任取一个元素(如第一个如第一个)为中心为中心全部比它小的元素一律前放，比它大的元素一全部比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；律后放，形成左
14、右两个子表；对各子表重新选择中心元素并依此规则调整，对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个直到每个子表的元素只剩一个一趟快速排序（一次划分）一趟快速排序（一次划分）目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动至该记录之前移动至该记录之前，反之，凡关键字大于枢轴关键字大于枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分分割成两部分：Rs.i-1和Ri+1.t，且Rj.keyRi.keyRj.key (sji-1)枢轴枢轴(i+1jt)。stlowhigh设
15、设 Rs=52 为枢轴为枢轴将Rhigh.key和枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字将Rlow.key和枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow可见，经过“一次划分一次划分”，将关键字序列 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;/
16、枢轴while(lowhigh)while(low=pivotkey)-high;/从右向左搜寻从右向左搜寻Rlow=Rhigh;while(lowhigh&Rlow.key=pivotkey)+low;/从左向右搜寻从左向右搜寻Rhigh=Rlow;Rlow=R0;returnlow;三、快速排序三、快速排序首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序voidQSort(RedType&R,ints,intt)/对记录序列Rs.t进行快速排
17、序if(st-1)/长度大于1/QSortpivotloc=Partition(R,s,t);/对Rs.t进行一次划分一次划分QSort(R,s,pivotloc-1);/对低子序列递归排序，pivotloc是枢轴位置是枢轴位置QSort(R,pivotloc+1,t);/对高子序列递归排序void QuickSort(SqList&L)/对依次表进行快速排序对依次表进行快速排序 QSort(L.r,1,L.length);/QuickSort第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。可以证明，平均计算时间是可以证明，平均计算时间是O(nlog2n)。试验
18、结果表明：就平均计算时间而言，快速排序是我试验结果表明：就平均计算时间而言，快速排序是我们所探讨的全部内排序方法中最好的一个。们所探讨的全部内排序方法中最好的一个。快速排序是递归的，须要有一个栈存放每层递归调用快速排序是递归的，须要有一个栈存放每层递归调用时参数（新的时参数（新的low和和high）。）。最大递归调用层次数与递归树的深度一样，因此，要最大递归调用层次数与递归树的深度一样，因此，要求存储开销为求存储开销为 O(log2n)。算法分析算法分析算法分析算法分析最好：划分后，左侧右侧子序列的长度相同最好：划分后，左侧右侧子序列的长度相同最坏：从小到大排好序，递归树成为单支树，每次最坏：
19、从小到大排好序，递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列，必需划分只得到一个比上一次少一个对象的子序列，必需经过经过 n-1 n-1 趟才能把全部对象定位，而且第趟才能把全部对象定位，而且第 i i 趟须要趟须要经过经过 n-i n-i 次关键码比较才能找到第次关键码比较才能找到第 i i 个对象的安放个对象的安放位置位置算法分析算法分析时间效率：时间效率：O(nlog2n)每趟确定的元素呈指数增加每趟确定的元素呈指数增加空间效率：空间效率：O（log2n）递归要用到栈空间递归要用到栈空间稳稳 定定 性：性：不稳定不稳定 可选任一元素为支点。可选任一元素为支点。10.4
20、10.4 选择排序选择排序基本思想：基本思想：每一趟在后面每一趟在后面 n-i+1个中选出关键码最小的对象个中选出关键码最小的对象,作作为有序序列的第为有序序列的第 i 个记录个记录简简 单单 选选 择择 排排 序序堆堆 排排 序序一、简洁选择排序一、简洁选择排序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列Ri.n第i趟简洁选择排序从中选出关键字最小的记录有序序列R1.i无序序列Ri+1.n212125*25*i=1=12525161649490808最小者最小者 0808交换交换交换交换21,0821,0825251616080825*25*49492121i=2=2最
21、小者最小者 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*25*i=5=54949最小者最小者 2525无交换无交换无交换无交换252521211616080825251616080825*25*49492121结果结果各趟排序后的结果各趟排序后的结果简洁选择排序简洁选择排序简洁选择排序的算法描述如下：void Se
22、lectSort(Elem R,int n)/对记录序列对记录序列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);/对对 H.r1 进行筛选进行筛选如何如何“建堆建堆”？两个问题两个问题:如何如何“调整调整”？定义堆类型为定义堆类型为:typedef SqList HeapType;/堆
23、接受依次表表示之堆接受依次表表示之 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 个元素起，至第一个元素止，进行反复个元素起，至第一个元素止，进行反复筛选筛选堆堆 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210 30 1 60
24、 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 12 810 7 1 2 3 4 5 6 7 3070124060810无序序列建成堆无序序列建成堆2 3 6 2 60 5 7040 4
25、 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建堆完毕建堆完毕将根结点将根结点r1与左、右子树根结点比较，并与左、右子树根结点比较，并与小者与小者交换交换重复重复直至叶子结点，得到新的堆直至叶子结点，得到新的堆
26、交换交换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 1706012403081070701060106010104040堆的重新调整堆的重新调整2 4010 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 560 1604
27、01210308107070堆的重新调整堆的重新调整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 1403012108601070706060堆的重新调整堆的重新调整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28
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 6 7 3 6 28 58 18101230860107070606040403030堆的重新调整堆的重新调整5 1030 4 8 6010
29、 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堆的重新调整堆的重新调整5 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706
30、060404030301212堆的重新调整堆的重新调整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(nlog2n)O(nlog2n)空间效率：空间效率：O O（1 1）稳稳 定定 性：不稳定性：不稳定适用于适用于n n 较大的状况较大的状况已知一组待排记录的关键字序列为(16，12
31、，18，60，15，36，14，18，25，85)，用堆排序方法堆排序方法堆排序方法堆排序方法建小根堆，请画出建堆的过程。练习：练习：10.5 10.5 归并排序归并排序归并：将两个或两个以上的有序表组合成一个新有序表归并：将两个或两个以上的有序表组合成一个新有序表2-2-路归并排序路归并排序排序过程排序过程初始序列看成初始序列看成n个个有序子序列，每个子序列长度为有序子序列，每个子序列长度为1两两合并两两合并，得到，得到 n/2 个长度为个长度为2或或1的有序子序列的有序子序列再两两合并，重复直至得到再两两合并，重复直至得到一个一个长度为长度为n的有序序的有序序列为止列为止将两个依次表合并成
32、一个有序表将两个依次表合并成一个有序表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 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490
33、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 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7
34、 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一趟归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三
35、趟归并后：13 27 38 49 65 76 97算法分析算法分析时间效率：时间效率：O(nlogO(nlog2 2n)n)空间效率：空间效率：O O（n n）稳稳 定定 性：性：稳定稳定 以扑克牌排序为例。每张扑克牌有两个以扑克牌排序为例。每张扑克牌有两个以扑克牌排序为例。每张扑克牌有两个以扑克牌排序为例。每张扑克牌有两个“排序码排序码排序码排序码”：花色和面值。其有序关系为：花色和面值。其有序关系为：花色和面值。其有序关系为：花色和面值。其有序关系为：花色：花色：花色：花色：面值：面值：面值：面值：2 3 4 5 6 7 8 9 10 J 2 3 4 5 6 7 8 9 10 J 2 3
36、4 5 6 7 8 9 10 J 2 3 4 5 6 7 8 9 10 J Q K AQ K AQ K AQ K 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 花色相同的状况下，比较面值。花色相同的状况下，比较面值。花色相同的状况下，比较面值。花色相同的状况下，比较面值。10.6 10.6 基数排序基数排序前面的排序方法主要通过关键字值之间的比较和移动前面的排序方法主要通过关键字值之间的比较
37、和移动前面的排序方法主要通过关键字值之间的比较和移动前面的排序方法主要通过关键字值之间的比较和移动而基数排序不须要关键字之间的比较而基数排序不须要关键字之间的比较而基数排序不须要关键字之间的比较而基数排序不须要关键字之间的比较对对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序：22 33 AA 22 33 AA 22 33 AA 22 33 A A两个关键字：花色（两个关键字：花色（）面值（面值（2323AA）并且并且“花色花色”地位高于地位高于“面值面值”多关键字排序多关键字排序链式基数排序链式基数排序uu最高位优先最高位优先最高位优先最高位优先MSD MSD MSD MSD(Mos
38、t 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 Significant Digit firstfirstfirstfirst)链式基数排序：用链式基数排序：用链表链表链表链表作存储结构的基数排序作
39、存储结构的基数排序先对先对最高位最高位关键字关键字k1k1（如花色）排序，将序列分如花色）排序，将序列分成若干子序列，每个子序列有相同的成若干子序列，每个子序列有相同的k1k1值；值；然后让每个子序列对然后让每个子序列对次关键字次关键字k2k2（如面值）排序，如面值）排序，又分成若干更小的子序列；又分成若干更小的子序列；依次重复，直至就每个子序列对依次重复，直至就每个子序列对最低位关键字最低位关键字kdkd排序排序，就可以得到一个有序的序列。，就可以得到一个有序的序列。最高位优先法最高位优先法十进制数比较可以看作是一个多关键字排序十进制数比较可以看作是一个多关键字排序十进制数比较可以看作是一个
40、多关键字排序十进制数比较可以看作是一个多关键字排序最高位优先法最高位优先法十位十位首先依据最低位排序码首先依据最低位排序码首先依据最低位排序码首先依据最低位排序码KdKdKdKd对全部对象进行一趟排序对全部对象进行一趟排序对全部对象进行一趟排序对全部对象进行一趟排序再依据次低位排序码再依据次低位排序码再依据次低位排序码再依据次低位排序码Kd-1Kd-1Kd-1Kd-1对上一趟排序结果排序对上一趟排序结果排序对上一趟排序结果排序对上一趟排序结果排序依次重复，直到依据排序码依次重复，直到依据排序码依次重复，直到依据排序码依次重复，直到依据排序码K1K1K1K1最终一趟排序完成，就最终一趟排序完成，
41、就最终一趟排序完成，就最终一趟排序完成，就可以得到一个有序的序列。可以得到一个有序的序列。可以得到一个有序的序列。可以得到一个有序的序列。最低位优先法最低位优先法这种方法不须要再分组，而是整个对象组都参与排序这种方法不须要再分组，而是整个对象组都参与排序这种方法不须要再分组，而是整个对象组都参与排序这种方法不须要再分组，而是整个对象组都参与排序最低位优先法最低位优先法先决条件：先决条件：先决条件：先决条件：知道各级关键字的知道各级关键字的主次关系主次关系知道各级关键字的知道各级关键字的取值范围取值范围链式基数排序链式基数排序利用利用“安排安排”和和“收集收集”对关键字进行排序对关键字进行排序过
42、程过程首先对低位关键字排序，各个记录依据此位首先对低位关键字排序，各个记录依据此位关键字的值关键字的值安排安排到相应的序列里。到相应的序列里。依据序列对应的值的大小，从各个序列中将依据序列对应的值的大小，从各个序列中将记录记录收集收集，收集后的序列依据此位关键，收集后的序列依据此位关键字有序。字有序。在此基础上，对前一位关键字进行排序。在此基础上，对前一位关键字进行排序。初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟
43、趟分分配配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集一趟收集008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配
44、配063083269278505589505008109930063269278083184589二趟收集二趟收集设置设置1010个队列，个队列，fifi和和eiei分别头指针和尾指针分别头指针和尾指针第一趟安排对最低位关键字（个位）进行，变更记第一趟安排对最低位关键字（个位）进行，变更记录的指针值，将链表中记录安排至录的指针值，将链表中记录安排至1010个链队列中，个链队列中，每个队列记录的关键字的个位相同每个队列记录的关键字的个位相同第一趟收集是变更全部非空队列的队尾记录的指针第一趟收集是变更全部非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将域，令其指向下一个非空队列
45、的队头记录，重新将1010个队列链成一个链表个队列链成一个链表重复上述两步，进行其次趟、第三趟安排和收集，重复上述两步，进行其次趟、第三趟安排和收集，分别对十位、百位进行，最终得到一个有序序列分别对十位、百位进行，最终得到一个有序序列链式基数排序步骤链式基数排序步骤n n重复执行重复执行重复执行重复执行d d d d趟趟趟趟“安排安排安排安排”与与与与“收集收集收集收集”n n每每每每趟趟趟趟对对对对 n n n n 个个个个记记记记录录录录进进进进行行行行“安安安安排排排排”，对对对对rdrdrdrd个个个个队队队队列列列列进进进进行行行行“收收收收集集集集”n n须要增加须要增加须要增加须
46、要增加n+2rdn+2rdn+2rdn+2rd个附加链接指针。个附加链接指针。个附加链接指针。个附加链接指针。n n个记录个记录个记录个记录每个记录有每个记录有每个记录有每个记录有 d d 位关键字位关键字位关键字位关键字关键字关键字关键字关键字取值范围取值范围取值范围取值范围rdrd(如十进制为如十进制为如十进制为如十进制为10)10)算法分析算法分析时间效率：时间效率：O(O(d(n+rd)d(n+rd)空间效率：空间效率：O(O(n+rd)n+rd)稳稳 定定 性：性：稳定稳定（数据不是（数据不是顺次后移顺次后移时将导致方法不稳定）时将导致方法不稳定）排序算法比较排序算法比较记忆口诀：（
47、1）平均时间困难度：以O（nlog2n）的速度快希归堆（看看这句话包括哪些排序），但是太快（快速排序）也不好，最坏达到O（n2）冒泡冒的好是O（n），冒得不好就是O（n2）干脆插入插得好，就是O（n），干脆插入插得不好就是O（n2）（2）空间困难度：记住特殊的三个：快速排序：O(logn)；归并排序：O(n)基数排序：O（dr）剩下的都是O(1)（3）稳定性：一句话解决，快希选一堆（玩具来玩）其中包括快速排序、希尔排序、简洁选择排序、堆排序！其他的全是稳定的按平均时间排序方法分为四类：按平均时间排序方法分为四类：O(nO(n2 2)、O(nlogO(nlogn n)、O(nO(n1+1+)快速
48、排序快速排序是基于比较的内部排序中平均性能最好的是基于比较的内部排序中平均性能最好的排序算法比较排序算法比较为避开依次存储时大量移动记录的时间开销，可考为避开依次存储时大量移动记录的时间开销，可考虑用链表作为存储结构虑用链表作为存储结构干脆插入排序、归并排序干脆插入排序、归并排序不宜接受链表作为存储结构的不宜接受链表作为存储结构的折半插入排序、希尔排序、快速排序、堆排折半插入排序、希尔排序、快速排序、堆排序序排序算法比较排序算法比较（1 1）分布随机，稳定性不做要求，则接受快速排序）分布随机，稳定性不做要求，则接受快速排序（2 2）内存允许，要求排序稳定时，则接受归并排序）内存允许，要求排序稳
49、定时，则接受归并排序（3 3）可可能能会会出出现现正正序序或或逆逆序序，稳稳定定性性不不做做要要求求，则则接接受堆排序或归并排序受堆排序或归并排序排序算法选择规则排序算法选择规则n较大时较大时（1 1）基本有序，要求稳定，则接受干脆插入排序）基本有序，要求稳定，则接受干脆插入排序（2 2）分布随机，稳定性不做要求，则接受干脆选择排）分布随机，稳定性不做要求，则接受干脆选择排序，若排序码不接近逆序，也可以接受干脆插入排序序，若排序码不接近逆序，也可以接受干脆插入排序n较小时较小时排序的概念排序的概念 定义定义 稳定性稳定性常用的排序算法常用的排序算法干脆插入排序、二分法插入排序、简洁选择排序干脆插入排序、二分法插入排序、简洁选择排序冒泡排序、希尔排序、快速排序、堆排序冒泡排序、希尔排序、快速排序、堆排序归并排序、基数排序归并排序、基数排序各类内部排序方法的特点各类内部排序方法的特点时间困难度、空间困难度、稳定性时间困难度、空间困难度、稳定性小结小结人有了学问，就会具备各种分析实力，明辨是非的实力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富学问，培育逻辑思维实力；通过阅读文学作品，我们能提高文学鉴赏水平，培育文学情趣；通过阅读报刊，我们能增长见识，扩大自己的学问面。有很多书籍还能培育我们的道德情操，给我们巨大的精神力气，鼓舞我们前进。