DS10_排序03_归并排序基数排序和各种内排的比较ppt课件.ppt

《DS10_排序03_归并排序基数排序和各种内排的比较ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章内部排序10.1排序的基本概念10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较10.5归并排序归并将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。归并排序的主要思想：将若干有序序列逐步归并，最终得到一个有序序列。二路归并排序基本思想：将n个记录的序列看成是n个长度为1的有序子序列；然后两两归并，得到个长度为2或1有序的子序列，再两两归并，...如此反复，直至得到一个长度为n的有序序列为止。例：关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过

2、程。212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整个归并排序仅需log2n趟关键问题：如何将两个有序序列合成一个有序序列？602031544556520605314455656020315445565ij5kj20i31j60kkkQ:归并可以就地进行吗?不可以，将归并的结果存入另外一个数组中。关键问题：如何将两个有序序列合成一个有序序列？602

3、031544556520605314455656020315445565ij5kj20i31j60关键问题：如何将两个有序序列合成一个有序序列？设相邻的有序序列为SR[i]~SR[m]和SR[m+1]~SR[n]，归并成一个有序序列TR[i]~r1[n]imm+1nSR[]inTR[]ijk//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]voidMerge(RcdTypeSR[]，RcdType&TR[]，inti，intm，intn){for(j=m+1，k=i;i<=m&&j<=n；++k){//将SR中记录由小到大并入TRif(LQ(SR[i].

4、key，SR[j].key))TR[k]=SR[i++];      elseTR[k]=SR[j++];}      if(i<=m)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//merge2-路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，其算法为：//将SR[s..t]归并排序为TR1[s..t]voidMSort(RcdTypeSR[]，RcdType&TR1[]，ints，intt){if(s==t)TR1[s]=SR[

5、s];else{m=(s+t)/2;//将SR[s..t]平分为SR[s..m]SR[m+1..t]Msort(SR,TR2,s,m)//递归地将SR[s..m]归并排序为有序的TR2[s..m]Msort(SR,TR2,m+1,t)//递归地将SR[m+1..t]归并排序为有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t)//将有序的TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]}}递归形式的2-路归并排序算法：//对顺序表L进行归并排序voidMergeSort(SqList&L){Msort(L.r，L.r，1，L.length)}特点：形

6、式简洁，效率很低归并排序分析在归并排序算法中，递归深度为O(log2n)，记录关键字的比较次数为O(nlog2n)。算法总的时间复杂度为O(nlog2n)。与快排相比优点：稳定、最坏情况O(nlog2n)缺点：空间复杂度O(n)ComparisonwithothersortalgorithmsAlthoughheapsorthasthesametimeboundsasmergesort,itrequiresonlyΘ(1)auxiliary(辅助)spaceinsteadofmergesort'sΘ(n),andisoftenfasterinpracticalimplementati

7、ons.Ontypicalmodernarchitectures,efficientquicksortimplementationsgenerallyoutperformmergesortforsortingRAM-basedarrays.Ontheotherhand,mergesortisastablesort,parallelizesbetter,andismoreefficientathandlingslow-to-accesssequentialm