数据结构第9章课件

9.1 9.1 概述概述9.2 9.2 插入类排序插入类排序9.3 9.3 交换类排序法交换类排序法9.4 9.4 选择类排序法选择类排序法9.5 9.5 归并归并类类排序排序9.6 9.6 分配类排序分配类排序9.7 9.7 外部排序外部排序第九章第九章 排序排序 9.8 9.8 总结与提高总结与提高一、排序的定义一、排序的定义排序是计算机内经常进行的一种操作，排序是计算机内经常进行的一种操作，其目的是将一组其目的是将一组“无序无序”的记录序列调整的记录序列调整为为“有序有序”的记录序列。的记录序列。例如：例如：将如下序列将如下序列52,49,80,36,14,58,61,23,97,75调整为调整为14,23,36,49,52,58,61,75,80,979.1 9.1 排序的基本概念排序的基本概念设含设含n 个记录的序列为个记录的序列为R1,R2,，Rn其相应的关键字序列为其相应的关键字序列为K1,K2,，Kn记录关键字相互之间可以进行比较，即存记录关键字相互之间可以进行比较，即存在关系在关系：Kp1Kp2Kpn按此关系将上述记录序列调整为按此关系将上述记录序列调整为Rp1,Rp2,，Rpn的操作称作的操作称作排序。排序。定义：定义：设待排序记录序列中有关键字相设待排序记录序列中有关键字相等的记录等的记录,即即ki=kj(ij),且在排序前且在排序前Ri领先于领先于Rj.若排序后若排序后可以保证可以保证Ri仍领先于仍领先于Rj,则则所用的排序方法称为所用的排序方法称为稳定的稳定的;若排序后若排序后不能保证不能保证Ri仍领先于仍领先于Rj,则则所用的排序方法称为所用的排序方法称为不稳定的不稳定的.二、稳定的排序和不稳定的排序二、稳定的排序和不稳定的排序例如：例如：排序前排序前(56,34,47,23,66,18,82,47)若排序后必有结果：若排序后必有结果：(18,23,34,47,47,56,66,82)则称该排序方法是则称该排序方法是稳定稳定的的;若排序后可能得结果：若排序后可能得结果：(18,23,34,47,47,56,66,82)则称该排序方法是则称该排序方法是不稳定不稳定的。的。若若整个排序过程不需要访问外存整个排序过程不需要访问外存便能完成，则称此类排序问题便能完成，则称此类排序问题为内部为内部排序。排序。反之反之,若参加排序的记录数量很若参加排序的记录数量很大大,整个序列的排序过程整个序列的排序过程不可能在内不可能在内存存中完成中完成，则称此类排序问题，则称此类排序问题为外为外部排序部排序。三、内部排序和外部排序三、内部排序和外部排序1、顺序存储：移动记录实现排序；、顺序存储：移动记录实现排序；2、(静态静态)链表：修改指针链表：修改指针(游标游标)实实现排序；现排序；3、地址向量：移动地址实现排序；、地址向量：移动地址实现排序；(又称地址排序又称地址排序)四、内部排序的存储方式四、内部排序的存储方式 本课程我们重点讨论在顺序存储结构本课程我们重点讨论在顺序存储结构上，各种排序方法的实现。上，各种排序方法的实现。排序算法的性能指标n执行时间和所需要的辅助空间n算法本身的复杂程度9.2 9.2 插入类排序插入类排序将无序序列中的记录将无序序列中的记录一个一个的一个一个的“插入插入”到有序序列中的到有序序列中的恰当恰当位置，以逐位置，以逐渐增加有序序列的长度渐增加有序序列的长度K(K=1N),从而实现排序。从而实现排序。基本思想：基本思想：有序序列r1.i-1ri无序序列 ri.n有序序列r1.i无序序列 ri+1.n找位置找位置插入插入一趟插入排序的基本过程：实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进行：3插入：插入：将将ri插入插入(复制复制)到到rj+1的的位置上。位置上。2后移：后移：将将rj+1.i-1中的所有记录均中的所有记录均后移一个位置；后移一个位置；1查找查找插入位置：插入位置：在在r1.i-1中查找中查找ri的插入位置的插入位置j+1：r1.j.key ri.keyrj+1.i-1.key；直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）利用“顺序查找顺序查找”实现“在r1.i-1中查找查找ri的插入位置的插入位置”算法的实现：算法的实现：一、直接插入排序一、直接插入排序1.从从ri-1起向前进行顺序查找，起向前进行顺序查找，循环结束确定循环结束确定ri的插入位置为的插入位置为j+1;r0jrij=i-1插入位置插入位置2.将所有将所有j+1i-1的记录向后移动的记录向后移动1位位;jjj3.将将r0(原原ri)“插入插入”到到j+1的位置的位置。监视哨设置在监视哨设置在r0；可以在查找的同时实现记录向后移动；可以在查找的同时实现记录向后移动；r0=ri;for(j=i-1;r0.keyrj.key;j-)；returnj+1;r0jrij=i-1上述循环结束后可以直接进行上述循环结束后可以直接进行“插入插入”插入位置插入位置方法的改进方法的改进:令令i=2,3,n,可实现整个序列的排序。可实现整个序列的排序。VoidInsertSort(RecordListL,)for(i=2；i=L.length;i+)L.r0=L.ri;for(j=i-1;L.r0.keyL.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.r0;算法：算法：稳定？稳定？改进后的直接插入排序nvoid InsertSort(RecordList L)for(i=2;i=L.length;i+)if(L.ri.keyL.ri-1.key)L.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）“比较比较”序列中两个关键字的序列中两个关键字的大小；大小；时间复杂度分析：时间复杂度分析：对于直接插入排序对于直接插入排序：最好的情况最好的情况(关键字在记录序列中顺序有序关键字在记录序列中顺序有序):“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：1=n-1ni=2(i+1)=ni=2(n+4)(n-1)2(i+1)=ni=2(n+4)(n-1)2所以，时间复杂度为所以，时间复杂度为O(n2)因为因为r1.i-1是一个按关键字有序是一个按关键字有序的序列的序列,则可以利用则可以利用折半查找折半查找实现在实现在“r1.i-1中查找中查找ri的插入位置的插入位置”,如此实现的插入排序为折半插入排序。如此实现的插入排序为折半插入排序。它只能它只能减少查找减少查找的次数的次数不能减少移动不能减少移动的的次数次数,因此与查找后移同时实现的直接因此与查找后移同时实现的直接插入排序比较插入排序比较,改进不大。改进不大。自学！自学！二、折半插入排序二、折半插入排序ilowhighmmlowlowhighilowhighmhighmhighmlow例如例如:再如再如:插入插入位置位置插入插入位置位置1436495280 5861239775L.r14364952586180 239775L.rm折半插入排序算法 void BiInsertSort(RecordList L)for(i=2;i=L.length;i+)if(L.ri.keyL.ri-1.key)L.r0=L.ri;low=1；high=i-1；while(low=high)mid=(low+high)/2;if(L.r0.key=low;j-)L.rj+1=L.rj;L.rlow=L.r0;由于由于插入排序的效率取决于插入排序的效率取决于:记录的个数记录的个数及记录的原始序；及记录的原始序；“宏观宏观”调整调整：先先“跳跃式跳跃式”的分组进行排序的分组进行排序,使得整个序列使得整个序列“基本有序基本有序”。(每组记录少每组记录少)“微观微观”调整调整：在整个序列在整个序列“基本有序基本有序”后后,再进行直接插入排序使整个序列再进行直接插入排序使整个序列“完全有序完全有序”。（记录的原始序。（记录的原始序优优）三三、希尔排序希尔排序(缩小增量排序缩小增量排序)所以所以希尔排序的基本思想为：希尔排序的基本思想为：对待排记录对待排记录序列先作序列先作“宏观宏观”调整，再作调整，再作“微观微观”调整。调整。将记录序列将记录序列跳跃式的跳跃式的分成若干组，分别对每组进分成若干组，分别对每组进行行插入排序，组数不断减少，最后仅剩一组。插入排序，组数不断减少，最后仅剩一组。其中其中,d 称为增量称为增量,它的值在排序过程中从它的值在排序过程中从大到小逐渐缩小大到小逐渐缩小,直至最后一趟排序直至最后一趟排序减为减为1.例如：将例如：将n个记录个记录r1,r2rd,r1+d,r2+dr2d,r1+2drn分成分成d个子序列：个子序列：r1，r1+d，r1+2d，,r1+kdr2，r2+d，r2+2d，,r2+kdrd,r2d,r3d,r(k+1)d具体做法：具体做法：例如：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 希尔排序算法 void ShellInsert(RecordList L,int dk)for(i=dk+1;i=L.length;i+)if(L.ri.key0&(L.r0.keyL.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.r0;nvoid ShellSort(RecordList L,int dlta,int t)for(k=0;kL.length;t+)ShellInsert(L,dltak);希尔排序的时间复杂度分析是一个希尔排序的时间复杂度分析是一个数学上尚未解决的难题。数学上尚未解决的难题。增量序列增量序列d1.t的设计至关重要，目前没有统一的设计至关重要，目前没有统一定论，以经验为主。定论，以经验为主。以经验，当以经验，当n在一定范围内时，在一定范围内时，希尔希尔排序的比较与移动次数约为：排序的比较与移动次数约为：n1.3,当当n时时:比较与移动次数约为比较与移动次数约为n(log2n)2。9.3 9.3 交换类排序法交换类排序法一、一、起泡排序起泡排序二、二、快速排序快速排序三、三、快速排序的时间分析快速排序的时间分析假设在排序过程中，记录序列假设在排序过程中，记录序列r1.n的状态为：的状态为：一一趟起泡排序趟起泡排序无序序列r1.i有序序列 ri+1.ni无序序列r1.i-1有序序列 ri.n对无序序列，比较对无序序列，比较(交交换换)相邻记录，可将关相邻记录，可将关键字最大的记录键字最大的记录交换交换到到i的位置上的位置上有序序列大于无序序列有序序列大于无序序列一、一、起泡排序起泡排序算法一：voidBubbleSort(RecordListL);flag=1;for(i=1;i=L.length-1&flag;i+)flag=0;flag=1;for(j=1;jL.length-i;j+)if(L.rj+1.key1)laste:=1;for(j=1;ji;j+)if(rj+1.keyrj.key)x=rj;rj=rj+1;rj+1=x;laste:=j;记下进行交换的记录位置记下进行交换的记录位置i:=laste;本趟最后一次进行交换的记录位置本趟最后一次进行交换的记录位置5231978注意注意:2.算法一每经过一趟“起泡”则“i i减1”，但算法二并不是每趟如此。例如例如:25531579 89i=7i=613i=21.起泡排序的结束条件为，最后一趟没有进行最后一趟没有进行“交换记录交换记录”。lastelaste1132最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-1(i-1)=ni=2n(n-1)23(i-1)=ni=23n(n-1)2所以，时间复杂度为所以，时间复杂度为O(n2)时间分析时间分析:起泡排序一趟之后，使最大的记录定起泡排序一趟之后，使最大的记录定位到位到最后最后,如果一趟之后可使某记录如果一趟之后可使某记录(任意任意)定位在它定位在它应处的位置应处的位置(在有序序列中在有序序列中),而将而将其余的无序序列以它为其余的无序序列以它为枢轴枢轴,分成两部分分成两部分,比它小的放在它的前面比它小的放在它的前面,比它大的的放在比它大的的放在它的后面它的后面,下一趟分别对前后的子序列排下一趟分别对前后的子序列排序序,显然可加快速度。显然可加快速度。这就是快速排序这就是快速排序二、快速排序二、快速排序目标：目标：找一个记录，找一个记录，以它的关键字作为以它的关键字作为“枢轴枢轴”，凡凡关键字小于枢轴关键字小于枢轴的记录均的记录均移移动至该记录之前，动至该记录之前，反之，凡反之，凡关键字大于枢关键字大于枢轴轴的记录均的记录均移动至该记录之后移动至该记录之后。致使致使一趟排序一趟排序之后，记录的无序序列之后，记录的无序序列rs.t将将分割成两部分分割成两部分：rs.i-1和和ri+1.t，且且rj.keyri.keyrj.key(sji-1)枢轴枢轴(i+1jt)。一趟快速排序（一次划分）一趟快速排序（一次划分）lowhigh设设rs=52为枢轴为枢轴将将rhigh.key和枢轴的关键字进行比较，和枢轴的关键字进行比较，要求要求rhigh.key枢轴的关键字枢轴的关键字将将rlow.key和和枢轴的关键字进行比较，枢轴的关键字进行比较，要求要求rlow.key枢轴的关键字枢轴的关键字highlowhighlow52498036145861972375strs 52highhighhighlowlow23801452例如例如可见，经过可见，经过“一次划分一次划分”，将关键字序列，将关键字序列52,49,80,36,14,58,61,97,23,75变为变为:23,49,14,36,(52)58,61,97,80,75在调整过程中，设立了两个指针：在调整过程中，设立了两个指针：low和和high，它们的初值分别为：，它们的初值分别为：s和和t，之后逐渐减小之后逐渐减小high，增加，增加low，并保证，并保证rhigh.key52，和，和rlow.key52,否则否则进行记录的进行记录的“交换交换”(实际只需赋值实际只需赋值)。一趟快速排序算法一趟快速排序算法intQKpass(RecordListL,intlow,inthigh)/*本算法对本算法对rs.t进行一趟快速排序进行一趟快速排序*/L.r0=L.rlow;while(lowhigh)/*low用用i表示表示,high用用j表示表示*/while(low=L.r0.key)-high;L.rlow=L.rhigh;while(lowhigh)&(rlow.key=L.r0.key)+low;L.rhigh=L.rlow;L.rlow=L.r0;returnlow;首先对无序的序列进行首先对无序的序列进行“一次划分一次划分”,之之后后分别分别对分割所得两个子序列对分割所得两个子序列“递归递归”进进行快速排序行快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序快速排序过程快速排序过程void QKSort(RecordList L,int low,int high);/*对记录序列对记录序列rs.t进行快速排序进行快速排序*/if (low high)pos=QKpass(L,low,high);/*对对 rs.t 进行一趟划分进行一趟划分,pos为枢轴为枢轴*/QKsort(L,low,pos-1);/*对低子序列递归排序对低子序列递归排序*/QKsort(L,pos+1,high);/*对高子序列递归排序对高子序列递归排序*/快速排序算法快速排序算法稳定？稳定？假设假设一次划分所得枢轴位置一次划分所得枢轴位置i=k，则，则对对n 个记录进行快速排序所需时间：个记录进行快速排序所需时间：其中其中Tpass(n)为对为对n 个记录进行一次划分个记录进行一次划分所需时间。所需时间。若待排序列中记录的关键字是随机分布的，若待排序列中记录的关键字是随机分布的，则则k取取1至至n中任意一值的可能性相同。中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)三、快速排序的时间分析三、快速排序的时间分析设设Tavg(0)b,Tavg(1)b,c,b为常数为常数则用数学归纳法可证明：则用数学归纳法可证明：Tavg(n)2n(b+c)ln(n)结论结论:快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的由此可得快速排序所需时间的平均值平均值为：为：Tavg(n)=cn+Tavg(k-1)+Tavg(n-k)nk=1n1=cn+Tavg(i)n-1i=1n2若待排记录的初始状态为按关键字有序若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，时，快速排序将蜕化为起泡排序，其时间其时间复杂度为复杂度为O(n2)。为避免出现这种情况，为避免出现这种情况，需在第一次划分需在第一次划分之前，进行之前，进行“予处理予处理”，即：即：先对先对rs.key,rt.key和和r(s+t)/2.key进行相互比较，然后进行相互比较，然后取取关关键字为键字为“中间中间”的记录的记录为枢轴为枢轴记录。记录。9.4 9.4 选择类排序法选择类排序法一、简一、简 单单 选选 择择 排排 序序二、树二、树 形形 选选 择择 排排 序序三、堆三、堆 排排 序序一、简单选择排序一、简单选择排序假设排序过程中假设排序过程中,待排记录序列的状态为：待排记录序列的状态为：有序序列有序序列r1.i-1无序序列无序序列ri.n第第i趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列r1.i无序序列无序序列ri+1.n有序序列有序序列小于小于无序序列无序序列简单选择排序算法简单选择排序算法voidSelectSort(RecordListL)for(i=1;i=L.length;i+)k=i；for(j=i+1;j=L.length-1;j+)if(L.rj.keyL.rk.key)k=j；if(k!=i)t=ri；ri=rk；rk=t;稳定？稳定？时间性能分析时间性能分析对对n个记录进行简单选择排序，个记录进行简单选择排序，所需进行的所需进行的关键字间的比较次数关键字间的比较次数总计为：总计为：移动记录的次数移动记录的次数：最小值为最小值为0最大值为最大值为3(n-1)。二、树形选择排序二、树形选择排序是一种按是一种按锦标赛锦标赛的思想进行排序的的思想进行排序的方法。方法。选择时两两比较选择时两两比较,第一轮小者为胜第一轮小者为胜者再进行第二轮比较者再进行第二轮比较,逐层向上直到比逐层向上直到比出冠军为最小者。出冠军为最小者。比较的过程是一个二叉树结构比较的过程是一个二叉树结构,其其中记录了互相之间的比较结果中记录了互相之间的比较结果,利用此利用此结果再比较很快会得到第二第三结果再比较很快会得到第二第三。010203040506070801030506010501按锦标赛规则，按锦标赛规则，05将成为将成为亚军亚军，显然，显然不合理不合理。解决。解决的方法是在的方法是在01夺冠夺冠之后，之后，01退出，退出，01参加过的比赛重参加过的比赛重新进行新进行（再筛选）。（再筛选）。020202如此，第二、第三如此，第二、第三各名次的结果才真实、各名次的结果才真实、合理。合理。由此，引出堆排序方法由此，引出堆排序方法(空间、时间效率更高空间、时间效率更高)三、堆排序三、堆排序堆是满足下列性质的数列堆是满足下列性质的数列r1,r2,，rn：或或堆的定义堆的定义:(小顶堆小顶堆)(大顶堆大顶堆)rir2ir2i+1可将该数列视作按层次存储的完全二叉树，可将该数列视作按层次存储的完全二叉树，则则r2i是是ri的左孩子；的左孩子；r2i+1是是ri的右孩子。的右孩子。例如例如:341236276549817355409812,36,27,65,40,34,98,81,73,55,49是堆是堆是小顶堆是小顶堆不不1412,36,27,65,40,14,98,81,73,55,49不是堆不是堆可利用可利用堆的特性堆的特性(首元素最小或最大首元素最小或最大)对记录序列进行排序！对记录序列进行排序！堆排序的特征堆排序的特征 堆排序是在排序过程中，将向量中堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树存储的数据看成一棵完全二叉树,利用完利用完全二叉树中双亲结点和孩子结点之间的全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，待排序记录仍采用向量数组方式存储，并非采用树的存储结构，仅仅是采用完并非采用树的存储结构，仅仅是采用完全二叉树顺序结构的特征进行分析处理。全二叉树顺序结构的特征进行分析处理。堆排序堆排序即是利用即是利用堆的特性堆的特性对记录序列对记录序列进行排序的一种排序方法进行排序的一种排序方法,过程如下：过程如下：1、对给定序列建堆；、对给定序列建堆；2、输出堆顶；、输出堆顶；(首元素与尾元素交换首元素与尾元素交换)3、对剩余元素重建堆；、对剩余元素重建堆；(筛选首元素筛选首元素)4、重复、重复2，3，直至所有元素输出。，直至所有元素输出。1、如何由一个无序序列、如何由一个无序序列“建堆建堆”？问题问题:2、输出堆顶后如何、输出堆顶后如何“重建堆重建堆”？两个问题均可归结为两个问题均可归结为“筛选筛选”问题？问题？建大顶堆 98,81,49,73,36,27,40,55,64,1212,81,49,73,36,27,40,55,64,98交换 9898 和 1212重新调整为大顶堆81,73,49,64,36,27,40,55,12,9840,55,49,73,12,27,98,81,64,36经过筛选 继续重复，可的有序序列。12,73,49,64,36,27,40,55,81,98交换 8181 和 1212例如：例如：所谓所谓“筛选筛选”指的是，对一棵左指的是，对一棵左/右子树均为右子树均为堆堆的完全二叉树，的完全二叉树，“调整调整”根结点根结点使整个二叉树也成为一个堆使整个二叉树也成为一个堆。堆堆堆堆筛筛选选814973556412362740是大顶堆是大顶堆但98 和12 互换后(去掉98),不不为堆。因此，需要对它进行“筛选筛选”(调整12)。981298比较比较比较981281736412建初堆也是一个建初堆也是一个“筛选筛选”的过程！的过程！例如例如:建初堆建初堆是从最后一个有孩子的结点开始，往是从最后一个有孩子的结点开始，往前逐个结点进行前逐个结点进行“筛选筛选”的过程。的过程。40554973816436122798例如给定的关键字序列为例如给定的关键字序列为:40,55,49,73,12,27,98,81,64,36123681734998817355 现在，左现在，左/右子树都已经调整为堆，最后只要右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个调整根结点，使整个二叉树是个“堆堆”即可。即可。98494064361227筛选算法筛选算法voidHeapAdjust（RecordListL,ints，int）/*调整调整rk，使整个序列，使整个序列rk.m满足堆的性质满足堆的性质*/t=L.rs；for(j=2*s;j=m;j*=2)if(jm&L.rj.keyL.rj+1.key)j=j+1；if(t.key=1;i-)HeapAdjust(L，i，L.length)；堆排序算法堆排序算法voidHeapSort（RecordListL）/*进行堆排序进行堆排序*/CreatHeap(L)；for(i=L.length;i=2;i-)L.r0=L.r1;L.r1=L.ri;L.ri=L.r0;/*将堆顶记录和堆中最后一个记录互换将堆顶记录和堆中最后一个记录互换*/HeapAdjust(L，1，i-1)；稳定？稳定？堆排序时间复杂度分析：堆排序时间复杂度分析：1.对深度为对深度为k的堆，的堆，“筛选筛选”所需进行的关键字所需进行的关键字比较的次数至多为比较的次数至多为2(k-1)；3.重建堆重建堆n-1次，所需进行的关键字比较的次数次，所需进行的关键字比较的次数不超过：不超过：(n-1)*2 log2n;因此，因此，堆排序的时间复杂度为堆排序的时间复杂度为(最坏情况最坏情况):):O(n*log2n+(n-1)*2 log2n)=O(nlogn)。2.n个关键字的堆深度为个关键字的堆深度为 log2n+1,初建初建堆堆所需所需进行的关键字比较的次数至多为：进行的关键字比较的次数至多为：n*log2n;9.5 9.5 归并排序归并排序归并排序的过程基于下列归并排序的过程基于下列基本思想基本思想进行：进行：将两个或两个以上的有序子序列将两个或两个以上的有序子序列“归并归并”为一个有序序列。为一个有序序列。在内部排序中，通常采用的是在内部排序中，通常采用的是2-路归并路归并排序。即：排序。即：将两个位置相邻的有序子序列将两个位置相邻的有序子序列归并为一个有序的序列归并为一个有序的序列。有有序序序序列列rl.n有序子序列有序子序列rl.m有序子序列有序子序列rm+1.n这个操作对顺序表而言，是轻而易举的。这个操作对顺序表而言，是轻而易举的。归归并并例：(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13,19,27)(01,16,26,31)(01,05,13,16,19,26,27,31)52,23,80,36,68,1452,23,8036,68,1452,23805223,5223,52,8036,6814366836,6814,36,6814,23,36,52,68,8023完整的归并排序过程为：先分组再归并。完整的归并排序过程为：先分组再归并。2-2-路归并排序算法路归并排序算法voidMergeSort(RecordList L,RecordList CopyL，int right,int left)int middle;if(leftright)middle=(left+right)/2；MergeSort(L，CopyL，left,middle)；MergeSort(L，CopyL,middle+1,right)；Merge(L，CopyL，left，right，middle)；稳定？稳定？合并算法合并算法voidMergeSort(RecordList L,RecordList CopyL，int right,int left)inti,p1,p2;for(i=left;i=right;i+)CopyL.ri=L.ri;i=left；p1=left；p2=middle+1；while(p1=middle)&(p2=right)if(CopyL.rp1.key=CopyL.rp2.key)L.ri=CopyL.rp1；p1+；elseL.ri=CopyL.rp2；p2+；i+；while(p1=middle)L.ri=CopyL.rp1；i+;p1+;while(p2=right)L.ri=CopyL.rp2；i+;p2+;自然归并排序归并排序的复杂度分析：归并排序的复杂度分析：容易看出，对容易看出，对n 个记录进行归并排序的个记录进行归并排序的时间复杂度为时间复杂度为(nlogn)。即：即：每一趟归并的时间复杂度为每一趟归并的时间复杂度为O(n)，总共需进行总共需进行 log2n 趟。趟。归并排序的空间复杂度较高，需要有长归并排序的空间复杂度较高，需要有长度为度为n的辅助数组，即为的辅助数组，即为O(n)。9.6 9.6 分配类排序分配类排序基数排序是一种基数排序是一种借助借助“多关键字排序多关键字排序”的思想来实现的思想来实现“单关键字排序单关键字排序”的内的内部排序算法。部排序算法。多关键字的排序多关键字的排序基数排序基数排序n个记录的序列个记录的序列R1,R2,，Rn对关键字对关键字 (Ki0,Ki1,Kid-1)有序有序是指是指：其中其中:K0被称为被称为 “最主最主/最高最高”位关键字位关键字Kd-1被称为被称为 “最次最次/最低最低”位关键字位关键字 对于序列中任意两个记录对于序列中任意两个记录Ri和和Rj(1ijn)都都满足满足下列下列(词典词典)有序有序关系：关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)一、多关键字的排序一、多关键字的排序 实现多关键字排序通常有两种方法实现多关键字排序通常有两种方法:最低位优先最低位优先LSD法法最高位优先最高位优先MSD法以扑克牌排序为例以扑克牌排序为例:将扑克牌的排序看成由将扑克牌的排序看成由花色花色和和面值面值两个关键字进两个关键字进行排序的问题。若规定花色和面值的顺序如下：行排序的问题。若规定花色和面值的顺序如下：花色：梅花花色：梅花 方块方块 红桃红桃 黑桃黑桃；面值：面值：A23A2310JQK10JQK；花色的优先级高于面值；花色的优先级高于面值；则一副牌从小到大的顺序为：则一副牌从小到大的顺序为：A,A,2,2,K K；A,A,2,2,K K；A,A,2,2,K K；A,A,2,2,K K。扑克牌的排序过程扑克牌的排序过程访法一访法一(LSD)：访法二访法二(MSD)：先先按按K0进行排序进行排序，并按，并按K0的不的不同值将记录序列同值将记录序列分成若干子序列分成若干子序列，之后之后再再分别分别按按K1进行排序进行排序，.，依次类推依次类推,直至最后直至最后分别分别按最次位按最次位关键字关键字Kd-1排序完成为止排序完成为止。最高位优先最高位优先MSD法：先按先按Kd-1进行排序进行排序，然后按然后按Kd-2进进行行稳定的稳定的排序，依次类推，直至按最主排序，依次类推，直至按最主位关键字位关键字K0排序完成为止排序完成为止。LSDLSD排序过程中不需要根据排序过程中不需要根据 “前一个前一个”关键字的排序结果，将记录序列分割关键字的排序结果，将记录序列分割成若干个子序列。成若干个子序列。最低位优先最低位优先LSD法：法：例例:学生记录含三个关键字学生记录含三个关键字:系别系别、班号班号和和班内的序列号班内的序列号，其中以，其中以系别系别为最主位关键字。为最主位关键字。无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,181,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下的排序过程如下:二、基数排序二、基数排序当当每个关键字的每个关键字的取值范围相同取值范围相同时，其排时，其排序可采用序可采用“分配分配”而非而非“比较比较”的方法进的方法进行。行。对于数字型或字符型的对于数字型或字符型的单关键字单关键字，可可以看成是由以看成是由多个多个数位数位或或多个多个字符字符构成的多构成的多关键字，而此时关键字，而此时每个每个“关键字关键字”的的取值范取值范围围是原关键字的是原关键字的基数。基数。对于数字型或字符型的对于数字型或字符型的“多关键字多关键字”,可用可用LSD法，并法，并采用采用“分配分配-收集收集”再再“分分配配-收集收集”的办法实现的办法实现排序排序,这就是这就是基数基数排序排序。例如：例如：对下列这组关键字对下列这组关键字369，367，167，239，237，138，230，139首先按其首先按其“个位数个位数”取值取值“分配分配”成成10组，之后按从组，之后按从0至至9的顺序将各组的顺序将各组“收集收集”在一起；在一起；然后按其然后按其“十位数十位数”取值取值“分配分配”成成10组，之后再按从组，之后再按从0至至9的顺序将各组的顺序将各组“收集收集”起来；起来；最后按其最后按其 “百位数百位数”取值取值“分配分配”成成10组，之后再按从组，之后再按从0至至9的顺序将各组的顺序将各组“收集收集”起来。起来。实现基数排序时，为减少所需辅助存储实现基数排序时，为减少所需辅助存储空间，可采用链表作存储结构。空间，可采用链表作存储结构。待排序记录以链表为存储结构；待排序记录以链表为存储结构；“分配分配”时，按时，按当前当前“关键字位关键字位”将记录将记录分分 配到不同的配到不同的 “链队列链队列”中，每个队列中中，每个队列中记记 录的录的 当前当前“关键字位关键字位”相同；相同；“收集收集”时，时，将各队列将各队列按关键字从小到大按关键字从小到大首首 尾相链尾相链构成一个新链表构成一个新链表;按按LSDLSD对每个关键字位重复对每个关键字位重复2、3,便可获便可获 得有序序列。得有序序列。具体方法：具体方法：p369367167239237138230139进行第一次分配进行第一次分配进行第一次收集进行第一次收集p230230367167237367167237138369239139369239139138f0 r0f7 r7f8 r8f9 r9例如：例如：进行第二次分配进行第二次分配p230237138239139p230367167237138369239139230 237138239139367 167369367167369进行第二次收集 f3 r3 f6 r6 进行第三次收集进行第三次收集p230237138239139367167369进行第三次分配进行第三次分配138 139167230 237239367 369p138139167230237239367369已得到记录的有序序列已得到记录的有序序列f1 r1f2 r2f3 r3 基数排序的时间复杂度为基数排序的时间复杂度为O(d(n+rd)其中：分配为其中：分配为O(n)收集为收集为O(rd)(rd为为“基基”)d为为“分配分配-收集收集”的趟数的趟数9.7 外部排序1.插入类插入类直接插入排序直接插入排序和和希尔排序希尔排序2.交换类交换类起泡排序起泡排序和和快速排序快速排序。3.选择类选择类4.归并类归并类5.分配类分配类基数排序基数排序简单选择排序简单选择排序和和堆排序堆排序归并排序归并排序9.9.8 8 算法总结算法总结排序方法排序方法 平均时间平均时间 最坏时间最坏时间 辅助空间辅助空间 稳定性稳定性简单排序简单排序 O(n2)O(n2)O(1)稳定稳定希尔排序希尔排序 O(n3/2)O(dk)非稳定非稳定快速排序快速排序 O(nlogn)O(n2)O(logn)非稳定非稳定堆排序堆排序O(nlogn)O(nlogn)O(1)非稳定非稳定归并排序归并排序 O(nlogn)O(nlogn)O(n)稳定稳定基数排序基数排序 O(d*n)O(d*n)O(rd)稳定稳定一、性能比较一、性能比较通过分析和比较，可以得出以下结论：通过分析和比较，可以得出以下结论：简单排序一般只用于简单排序一般只用于n n值较小的情况；值较小的情况；归并排序适用于归并排序适用于n n值较大的情况；值较大的情况；基数排序适用于基数排序适用于n n值很大而关键字的位数值很大而关键字的位数d d较较小的序列；小的序列；快速排序是排序方法中最快速排序是排序方法中最“快快”的方法。的方法。本章讨论的各种排序方法，除基数排序本章讨论的各种排序方法，除基数排序外，其它方法都是外，其它方法都是基于基于“比较比较”进行排序进行排序的排序方法。的排序方法。可以证明可以证明,这类排序法这类排序法可能达到的最快可能达到的最快的时间复杂度为的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。)二、内部排序时间复杂度下限分析二、内部排序时间复杂度下限分析例如例如:对三个关键字进行排序的判定树对三个关键字进行排序的判定树如下：如下：K1K3K1K2K1K3K2K3K2K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2树上的树上的每一次每一次“比较比较”都是都是必要必要的的;树上的树上的叶子叶子代表代表所有可能的排序结果所有可能的排序结果。nynnnn一般而言一般而言,对对n个关键字进行排序个关键字进行排序,可得可得到的结果有到的结果有n!种种(n!个叶子个叶子),由于含由于含n!个个叶子的二叉树的深度不小于叶子的二叉树的深度不小于 log2(n!)+1,所以对所以对n 个关键字进行排序的比较次数至个关键字进行排序的比较次数至少是少是 log2(n!)nlog2n(斯蒂林近似公式斯蒂林近似公式)。所以所以,基于基于“比较关键字比较关键字”进行排序进行排序的的排序方法排序方法,可能达到的最快的时间复杂度可能达到的最快的时间复杂度为为O(nlogn)。1.1.了解排序的定义和各种排序方法的特点。了解排序的定义和各种排序方法的特点。熟练掌握各种排序方法及各种排序方法排熟练掌握各种排序方法及各种排序方法排序时每趟的变化过程。序时每趟的变化过程。插入排序（插入排序（希尔希尔）；交换排序（）；交换排序（快速快速）；）；选择排序（选择排序（堆堆）；）；归并排序；归并排序；基于基于“分配分配-收集收集”的基数排序。的基数排序。9.8 9.8 总结与提高总结与提高2、掌握各种排序方法的时间复杂度掌握各种排序方法的时间复杂度的分析方法。能从的分析方法。能从“关键字间的比较次关键字间的比较次数数”分析排序算法的平均情况和最坏情分析排序算法的平均情况和最坏情况的时间性能。况的时间性能。按平均时间复杂度划分按平均时间复杂度划分,内部排序可分内部排序可分为三类：为三类：O(n2)的简单排序方法、的简单排序方法、O(nlogn)的高效排序方法和的高效排序方法和O(dn)的基数排序方法。的基数排序方法。3理解排序方法理解排序方法“稳定稳定”或或“不稳定不稳定”的含义，弄清楚在什么情况下要求应的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。用的排序方法必须是稳定的。4.了解外部排序的基本过程及其时间了解外部排序的基本过程及其时间分析分析。典型例题：典型例题：例例1 1：设有：设有1000010000个元素，要求找出最小的个元素，要求找出最小的1010个，个，选择合适的排序方法。选择合适的排序方法。例例2 2：n=7时，给出快速排序最好情况的初始序列。时，给出快速排序最好情况的初始序列。堆排序！堆排序！4，1，3，2，6，5，7例例3 3 哈希排序：设有哈希排序：设有300300个记录，其关键字均为个记录，其关键字均为小于小于10001000的正整数，且互不相等。设计一排序的正整数，且互不相等。设计一排序方法，比较移动次数尽可能少。方法，比较移动次数尽可能少。设置辅助数组设置辅助数组b1.999,b1.999,按哈希法将记录分配按哈希法将记录分配,再回收再回收例例4荷兰国旗问题：荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的色条设有一个仅由红、白、蓝三种颜色的色条组成的序列，要求在组成的序列，要求在O(nO(n)的时间内将其排列的时间内将其排列成荷兰国旗。成荷兰国旗。例如：例如：初始序列为初始序列为 蓝蓝,白白,红红,白白,蓝蓝,红红,白白,白白,红红,蓝蓝 要求排列结果为要求排列结果为 红红,红红,红红,白白,白白,白白,白白,蓝蓝,蓝蓝,蓝蓝 算法选择：算法选择：1 1、简单选择排序思想；、简单选择排序思想；2 2、快速排序思想；、快速排序思想；3 3、基数排序思想。、基数排序思想。两趟选择：第1趟选红色，第2趟选白色。算法见P333.经过1趟分配、收集即可。荷兰国旗问题的快速排序算法荷兰国旗问题的快速排序算法设设3 3个指示器个指示器r,w,br,w,b,指示各区下一个单元；初始时：指示各区下一个单元；初始时：r=w=0;b=n-1,wr=w=0;b=n-1,w相当于相当于low,blow,b相当于相当于highhigh处理处理;最终最终:1.r-1:1.r-1红色红色,r.w-1,r.w-1白色，白色，w.n-1w.n-1蓝色。蓝色。Voidsord(intL,intn)intx,r,w,b;r=w=0;b=n-1while(w=b)x=LW;if(x=1)Lw=Lr;w+;Lr=x;r+;elseif(x=2)w+;elseLw=Lb;Lb=x;b-;第九章结束第九章结束Voidshellinsert(recordtyper,intn,intd)for(i=1+d;in;i+)if(ri.key0&r0.keyrj.key;j-=d)rj+d=rj;rj+d=r0;Void shellsord(recordtype r,int length,int d,int n)for(i=0;i=n-1,+i)shellinsert(r,length,di);希尔算希尔算法：法：稳定？稳定？存储结构：存储结构：为有效地存储和重排记录，算法采用静态为有效地存储和重排记录，算法采用静态链表，有关数据类型的定义如下：链表，有关数据类型的定义如下：#define RADIX 10#define RADIX 10#define KEY_SIZE 6#define KEY_SIZE 6#define LIST_SIZE 20#define LIST_SIZE 20typedeftypedef intint KeyTypeKeyType;typedeftypedef structstruct KeyTypeKeyType keysKEY_SIZEkeysKEY_SIZE;/*;/*子关键字数组子关键字数组*/OtherTypeOtherType other_dataother_data;/*;/*其它数据项其它数据项*/intint next;/*next;/*静态链域静态链域*/RecordType1;RecordType1;typedeftypedef structstruct RecordType1 rLIST_SIZE+1;/*r0 RecordType1 rLIST_SIZE+1;/*r0为头结点为头结点*/intint length;length;intint keynumkeynum;SLinkListSLinkList;/*;/*静态链表静态链表*/typedeftypedef intint PVectorRADIXPVectorRADIX;分配算法：分配算法：voidDistribute(RecordType1 rRecordType1 r,inti,PVectorPVector head,PVectorPVector tail)/*数数组组r已已按按低低位位关关键键字字keyi+1，keyd进进行行了了“低低位位优优先先”排排序序*/for(j=0;j=RADIX-1RADIX-1;+j)headj=0；/*将将RADIXRADIX个个队列初始化为空队列队列初始化为空队列*/p=r0.next；/*p指向链表中的第一个记录指向链表中的第一个记录*/while(p!=0)j=Order(rp.keyi)；/*用第用第i位关键字求相应队列号位关键字求相应队列号*/if(headj=0)headj=p;/*将将p结点加入第结点加入第j队列队列*/elsertailj.next=p；tailj=p；p=rp.next；voidCollect(RecordTypeRecordType r r,PVectorPVector head,PVectorPVector tail)/*从从0到到RADIX-1RADIX-1扫描各队列，将非空队列首尾相接成一个链表扫描各队列，将非空队列首尾相接成一个链表*/j=0；while(headj=0)+j；/*找第一个非空队列找第一个非空队列*/r0.next=headj；t=tailj；while(jRADIX-1RADIX-1)/*寻找并串接所有非空队列寻找并串接所有非空队列*/+j；while(jRADIX-1RADIX-1)&(headj=0)+j；/*找下一个非空队列找下一个非空队列*/if(headj!=0)/*链接非空队列链接非空队列*/rt.next=headj；t=tailj；rt.next=0;/*t指向最后一个非空队列中的最后一个结点指向最后一个非空队列中的最后一个结点*/收集算法：收集算法：基数排序算法：基数排序算法：voidRadixSort(RecordTypeRecordType r,intr,int length length)/*lengthlength个记录存放在数组个记录存放在数组r中，进行基数排序中，进行基数排序*/n=length；for(i=0;i=0;-i)/*从最低位子关键字开始，进行从最低位子关键字开始，进行d趟分配趟分配和和收集收集*/Distribute(r，i，head，tail)；/*第第i趟分配趟分配*/Collect(r，head，tail)/*第第i趟收集趟收集*/