数据结构第二十二讲

第二十二讲1、2、总复习110.5归并排序归并排序(MergeSort)也是一种常用的排序方法，“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。如图8-11为两组有序表的归并，有序表{4,25,34,56,69,74}和{15,26,34,47,52}，通过归并把它们合并成一个有序表{4,15,25,26,34,34,47,52,56,69,74}。图8-11两组有序表的归并2二路归并排序的基本思想是：将有n个记录的待排序列看作n个有序子表，每个有序子表的长度为1，然后从第一个有序子表开始，把相邻的两个有序子表两两合并，得到n/2个长度为2或1的有序子表（当有序子表的个数为奇数时，最后一组合并得到的有序子表长度为1），这一过程称为一趟归并排序。再将有序子表两两归并，如此反复，直到得到一个长度为n的有序表为止。上述每趟归并排序都需要将相邻的两个有序子表两两合并成一个有序表，这种归并方法称为二路归并排序。31．两个有序表的合并算法Merge()。设线性表R[low..m]，和R[m+1..high]是两个已排序的有序表，存放在同一数组中相邻的位置上，将它们合并到一个数组Rl中，合并过程如下：(1)比较线性表R[low..m]与R[m+1..high]的第一个记录，将其中关键字值较小的记录移入表R1(如果关键字值相同，可将R[low..m]的第一个记录移入R1中)。(2)将关键字值较小的记录所在线性表的长度减1，并将其后继记录作为该线性表的第一个记录。反复执行上述过程，直到线性表R[low..m]或R[m+1..high]之一成为空表，然后将非空表中剩余的记录移入R1中，此时Rl成为一个有序表。算法描述如下：4voidMerge(RecTypeR[],RecTypeR1[],intlow,intm,inthigh){//R[low..m]和R[m+1..high]是两个有序表inti=low,j=m+l,k=low;//k是Rl的下标，i、j分别为R[low..m]和R[m+1..high]的下标

while(i<=m&&j<=high){

//在R[low..m]和R[m+1..high]均未扫描完时循环

if(R[i].key<=R[j].key){//将R[low..m]中的记录放入R1中

R1[k]=R[i];i++;k++;

}else{//将R[m+1..high]中的记录放入R1中

R1[k]=R[j];j++;k++;

}}5while(i<=m){//将R[low..m]余下部分复制到R1

R1[k]=R[i];i++;k++;}

while(j<=high){//将R[m+1..high]余下部分复制到R1

R1[k]=R[j];

j++;k++;}}62．一趟归并排序的算法MergePass()。一趟归并排序的算法调用n/(2*length)次归并算法merge()，将R[1..n]中前后相邻且长度为length的有序子表进行两两归并，得到前后相邻且长度为2*length的有序表，并存放在R1[1..n]中。如果n不是2*length的整数倍，则可出现两种情况：一种情况是，剩下一个长度为length的有序子表和一个长度小于length的子表，合并之后其有序表的长度小于2*length；另一种情况是，只剩下一个子表，其长度小于等于length，此时不调用算法merge()，只需将其直接放入数组R1中，准备进行下一趟归并排序。算法描述如下：7voidMergePass(RecTypeR[],RecTypeR1[],intlength,intn){inti=0,j;while(i+2*length-l<n){Merge(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;//归并长度为length的两相邻有序子表

}

if(i+length-1<n-1)//余下两个有序子表，其中一个长度小于lengh

Merge(R,R1,i,i+length-1,n-1);//归并两个有序表

else

for(j=i;j<n;j++)//剩下一个有序子表，其长度小于lengh

R1[j]=R[j];}83．归并排序算法Merge­­_Sort()两路归并排序需要由多趟归并过程实现。第一趟length=1，以后每执行一趟归并后将length加倍。第一趟归并的结果存放在R1中；第二趟将数组R1中的有序子表两两合并，结果存放在数组R中；如此反复进行。为使最终排序结果存放在数组R中，进行归并的趟数必须是偶数。因此当只需奇数趟归并即可完成排序时，应再进行一趟归并，只是此时只剩下一个长度不大于length的有序表，直接从数组R1复制到R中即可。算法描述如下：voidMerge­­_Sort(RecTypeR[],intn){intlength=1;while(length<n){MergePass(R,R1,length,n);length=2*length;MergePass(R1,R,length,n);length=2*length;}}9【例10-8】初始序列为｛23，56，42，37，15，84，72，27，18｝用二路归并排序法排序。【解】排序后的结果为：｛15，18，23，27，37，42，56，72，84｝，整个归并过程如图8-12所示。图10-12归并排序示例10显然，n个记录进行二路归并排序时，归并的趟数为O(log2n)，每趟归并中，关键字的比较次数不超过n，因此，二路归并排序的时间复杂度为O(nlog2n)。对序列进行归并排序时，除采用二路归并排序外，还可以采用多路归并排序方法（可参考其它有关书籍）。归并排序需要的辅助空间R1与待排序记录的数量相等，因此二路归并排序的空间复杂度为O(n)，这是常用的排序方法中空间复杂度最差的一种排序方法。另外，从排序的稳定性看，二路归并排序是一种稳定的排序方法。1110.6各种排序方法的比较在前面几节中讨论了内部排序的方法。对于内部排序主要介绍了四大类排序方法：插入排序（直接插入排序、折半插入排序和希尔排序）、交换排序（冒泡排序和快速排序）、选择排序（简单选择排序和堆排序）、归并排序。详细讨论了各种排序方法的基本原理，并从时间复杂性、空间复杂性以及排序的稳定性三方面讨论了各种排序方法的时效性，介绍了各排序方法的实现算法及其存在的优缺点。如果待排序的数据量很小，最好选择编程简单的排序算法，因为在这种情况下采用编程复杂、效率较高的排序方法所能节约的计算机时间是很有限的。反之，如果待处理的数据量很大，特别是当排序过程作为应用程序的一部分需要经常执行时，就应该认真分析和比较各种排序方法，从中选出运行效率最高的方法。12下面具体比较一下各种排序方法，以便实现不同的排序处理。(1)插入排序的原理：向有序序列中依次插入无序序列中待排序的记录，直到无序序列为空，对应的有序序列即为排序的结果，其主旨是“插入”。(2)交换排序的原理：先比较大小，如果逆序就进行交换，直到有序。其主旨是“若逆序就交换”。(3)选择排序的原理：先找关键字最小的记录，再放到已排好序的序列后面，依次选择，直到全部有序，其主旨是“选择”。(4)归并排序的原理：依次对两个有序子序列进行“合并”，直到合并为一个有序序列为止，其主旨是“合并”。(5)基数排序的原理：按待排序记录的关键字的组成成分进行排序的一种方法，即依次比较各个记录关键字相应“位”的值，进行排序，直到比较完所有的“位”，即得到一个有序的序列。各种排序方法的工作原理不同，对应的性能也有很大的差别，下面通过一个表格可以看到各排序方法具体的时间性能、空间性能等方面的区别。13表10-2内部排序方法的时间性能、空间性能表14依据这些因素，可得出如下几点结论：(1)若n较小（如n值小于50），对排序稳定性不作要求时，宜采用选择排序方法，若关键字的值不接近逆序，亦可采用直接插入排序法。但如果规模相同，且记录本身所包含的信息域比较多的情况下应首选简单选择排序方法。因为直接插入排序方法中记录位置的移动操作次数比直接选择排序多，所以选用直接选择排序为宜。(2)如果序列的初始状态已经是一个按关键字基本有序的序列，则选择直接插入排序方法和冒泡排序方法比较合适，因为“基本”有序的序列在排序时进行记录位置的移动次数比较少。(3)如果n较大，则应采用时间复杂度为O(nlog2n)的排序方法，即快速排序、堆排序或归并排序方法。快速排序是目前公认的内部排序的最好方法，当待排序的关键字是随机分布时，快速排序所需的平均时间最少；堆排序所需的时间与快速排序相同，但辅助空间少于快速排序，并且不会出现最坏情况下时间复杂性达到O(n2)的状况。这两种排序方法都是不稳定的，若要求排序稳定则可选用归并排序。通常可以将它和直接插入排序结合在一起用。先利用直接插入排序求得两个子文件，然后，再进行两两归并。15前面讨论的排序算法，除基数排序外，都是在一维数组上实现的，当记录本身信息量较大时，为了避免移动记录而浪费大量的时间，可以采用链表作为存储结构，如插入排序和归并排序都易于在链表上实现；但有的方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后，对索引表进行排序。然而更为简单的方法是引入一个整型向量作为辅助表。排序前，若排序算法中要求交换，则只需交换相对应的向量，而无需交换具体的记录内容；排序结束后，向量就指示了记录之间的顺序关系。16本章小结

排序是软件设计中最常用的运算之一。排序分为内部排序和外部排序，涉及多种排序的方法。内部排序是将待排序的记录全部放在内存的排序。本章所讨论的各种内部排序的方法大致可分为：插入排序、交换排序、选择排序、归并排序和基数排序。插入排序算法的基本思想是：将待序列表看做是左、右两部分，其中左边为有序序列，右边为无序序列，整个排序过程就是将右边无序序列中的记录逐个插入到左边的有序序列中。直接插入排序是这类排序算法中最基本的一种，然而，该排序法时间性能取决于待排序记录的初始特性。折半插入排序是通过折半查找的方法在有序表中查找记录插入位置的排序方法。希尔排序算法是一种改进的插入排序，其基本思想是：将待排记录序列划分为若干组，在每组内先进行直接插入排序，以使组内序列基本有序，然后再对整个序列进行直接插入排序。其时间性能不取决于待排序记录的初始特性。17交换排序的基本思想是：两两比较待排序列的记录关键字，发现逆序即交换。基于这种思想的排序有冒泡排序和快速排序两种。冒泡排序的基本思想是：从一端开始，逐个比较相邻的两个记录，发现逆序即交换。然而，其时间性能取决于待排序记录的初始特性。快速排序是一种改进的交换排序，其基本思想是：以选定的记录为中间记录，将待排序记录划分为左、右两部分，其中左边所确记录的关键字不大于右边所有记录的关键字，然后再对左右两部分分别进行快速排序。18选择排序的基本思想是：在每一趟排序中，在待排序子表中选出关键字最小或最大的记录放在其最终位置上。直接选择排序和堆排序是基于这一思想的两个排序算法。直接选择排序算法采用的方法较直观：通过对待排序子表中完整地比较一遍以确定最大(小)记录，并将该记录放在子表的最前(后)面。堆排序就是利用堆来进行的一种排序，其中堆是一个满足特定条件的序列，该条件用完全二叉树模型表示为每个结点不大于(小于)其左、右孩子的值。利用堆排序可使选择下一个最大(小)数的时间加快，因而提高算法的时间复杂度，达到O(nlog2n)。归并排序是一种基于归并的排序，其基本操作是指将两个或两个以上的有序表合并成一个新的有序表。首先将n个待排序记录看成n个长度为1的有序序列，第一趟归并后变成n/2个长度为2或1的有序序列；再进行第二趟归并，如此反复，最终得到一个长度为n的有序序列。归并排序的时间复杂度为O(nlog2n)，最初待排序记录的排列顺序对运算时间影响不大，不足之处就是需要占用较大的辅助空间。1919．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用的排序是()。选择B.冒泡C.快速D.插入22．下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序AB2023．下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。选择B.冒泡C.归并D.堆26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)CC2143．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}44．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)AB2248.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序50.以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)DD2351．下列四个序列中，哪一个是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1552.堆排序是（）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（）

A.插入B.交换C.归并D.基数E.选择

F.O（n2）和O（1）G.O（nlog2n）和O（1）H.O（nlog2n）和O（n）I.O（n2）和O（n）CEG241、选择题（40分，20道*2），考查基本概念，基本原理；2、填空题（10分，10个空*2），考查基本概念，基本原理，部分简单操作和程序的编写；3、应用题（操作