算法21内部排序归并排序.ppt

,第9章内部排序,2,9.1概述9.2插入排序9.3快速排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序方法的比较,第9章内部排序,3,归并的定义,又叫合并，两个或两个以上的有序序列合并成一个有序序列。,9.5归并排序,基本思想：将两个（或以上）的有序表组成新的有序表。实际的意义：可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到n/2个长度为2的子序列；再做两两归并，如此重复，直到最后得到一个长度为n的有序序列。,9.5归并排序,2020/5/21,归并排序,voidMerge(SR，/将剩余的SRjn复制到TR/Merge,一趟归并排序算法(两路有序并为一路),2020/5/21,例：关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n趟,9,例：合并两个已排序的有序表。将下面两个已排序的有序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中一表为空为止，将另一表中剩余结点自左至右复制到表C的剩余位置。,01234,36,20,65,97,76,7,80,A,B,01234567,C,i,j,k,9.5归并排序,10,归并实例,01234,36,20,65,97,76,7,80,A,B,C,i,j,k,7,01234567,11,01234,36,20,65,97,76,7,80,A,B,C,7,01234567,归并实例,12,01234,36,20,65,97,76,7,80,A,B,C,7,20,01234567,归并实例,13,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,01234567,归并实例,14,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,01234567,归并实例,15,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,01234567,归并实例,16,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,01234567,归并实例,17,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,76,01234567,归并实例,18,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,76,01234567,归并实例,19,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,76,80,01234567,归并实例,20,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,76,80,至此B表的元素都已移入C表，只需将A表的剩余部分移入C表即可。,01234567,归并实例,21,01234,36,20,65,97,76,7,80,A,B,C,7,20,36,65,76,80,至此B表的元素都已移入C表，只需将A表的剩余部分移入C表即可。,97,01234567,归并实例,22,归并算法(一路无序变为有序),voidMsort(RcdTypeSR,RcdType/将TR2s.m和TR2m+1.t归并到TR1s.t/Msort,2020/5/21,递归与分治法,归并排序算法是用分治策略实现对n个元素进行排序的算法。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,2020/5/21,实现这种递归调用的关键是为过程建立递归调用工作栈。通常，在一个过程中调用另一过程时，系统需在运行被调用过程之前先完成3件事:（1）将所有实参指针，返回地址等信息传递给被调用过程；（2）为被调用过程的局部变量分配存储区；（3）将控制转移到被调用过程的入口。在从被调用过程返回调用过程时，系统也相应地要完成3件事：（1）保存被调用过程的计算结果；（2）释放分配给被调用过程的数据区；（3）依照被凋用过程保存的返回地址将控制转移到调用过程.,2020/5/21,分治法的基本思想,分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。,2020/5/21,它的一般的算法设计模式如下：procedureDivide_and_Conquer(P，y)；beginif|P|n0thenbeginADHOC(P)；return/基本子算法end；dividePintosmallersuhinstancesP1，P2，Pk；fori1tokdoDivide_and_Conquer(Pi,yi)；MERGE(yl，yk，y)；returnend；,2020/5/21,|P|表示问题P的规模。N0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。算法MERGE(yl，yk，y)是该分治法中的合并子算法,2020/5/21,在用分治法设计算法时，最好使子问题的规模大致相同。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。,2020/5/21,为方便起见，设分解阈值n0=1，且ADHOC解规模为1的问题耗费1个单位时间。又设分治法将规模为n的问题分成k个规模为nm的子问题去解，而且将原问题分解为是个子问题以及用MERGE将是个子问题的解合并为原问题的解需用f(n)个单位时间。T(1)=1T(n)=kT(n/m)+f(n),30,归并排序时间复杂性分析,合并趟数：log2n每趟进行比较的代价n总的代价为T(n)=O(nlog2n)在一般情况下：cn=1T(n)=T(n/2)+T(n/2)+cnn1解上述的递归式，可知时间复杂性为T(n)=O(nlog2n)。,2020/5/21,“”符号(渐进上界),设f(N)和g(N)是定义在正数集上的正函数。如果存在正的常数c和自然数N0，使得当NN0时有f(N)cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=(g(N)。这时我们还说f(N)的阶不高于g(N)的阶。,2020/5/21,2020/5/21,按照大O的定义，容易证明它有如下运算规则：,O(f)O(g)O(max(f，g)；O(f)O(g)O(fg)；O(f)O(g)=O(fg)；如果g(N)O(f(N)，则O(f)+O(g)=O(f)；O(Cf(N)=O(f(N)，其中C是一个正的常数；fO(f)；其中f=f(N)，g=g(N)，max(f,g)=,2020/5/21,记号“”(渐进下界),定义如下：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=(g(N)这时我们还说f(N)的阶不低于g(N)的阶。优缺点：的这个定义的优点是与O的定义对称，缺点是当f(N)对自然数的不同无穷子集有不同的表达式，且有不同的阶时，未能很好地刻画出f(N)的下界。,2020/5/21,2020/5/21,代入法解递归方程,方法的关键步骤在于预先对解答作出推测，然后用数学归纳法证明推测的正确性。例如：我们要估计T(n)的上界，T(n)满足递归方程：其中是地板(floors)函数的记号。推测T(n)O(nlogn)，即推测存在正的常数C和自然数n0，使得当nn0时有：T(n)Cnlogn0,2020/5/21,取n0=22=4，并取那么，当n0n2n0时，T(n)Cnlogn成立。今归纳假设当:，当k1时，T(n)Cnlogn成立。,证明：,2020/5/21,T(n)2T(n2)+n2Cn2log(n2)+n2C(n/2)log(n/2)+nCnlogn-Cn+nCnlogn-(C-1)nCnlogn结论：递归方程式的解的渐近阶O(nlogn)。,那么，当时，我们有：,2020/5/21,局限性：,这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手。推测递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。,2020/5/21,（1）如果一个递归方程类似于你从前见过的已知其解的方程，那么推测它有类似的解是合理的。例如:考虑递归方程：T(n)2T(n2+17)+n有类似的上界T(n)O(nlogn)。进一步，数学归纳将证明此推测是正确的。（2）从较宽松的界开始推测，逐步逼近精确界。T(n)=(n)太松T(n)=(nlogn)的精确估计。,（3）作变元的替换,例如：考虑递归方程：设mlogn，即令n=2m,将其代入，则变成：，把m限制在正偶数集上，则式又可改写为：若令S(m)=T(2m)，则S(m)满足的递归方程：因而有：S(m)=O(mlogm)，T(n)=T(2m)=S(m)=O(mlogm)=O(lognloglogn),42,归并排序空间复杂性及稳定性分析,时间复杂度：O(nlog2n)空间复杂度：O(n)稳定性：稳定归并排序是将数组不断的二分直至子数组长度为1，然后再开始合并，因此它的时间复杂度只与数组长度相关，而每一层的比较次数都是O(n)级别，共logn层，所以时间复杂度是O(nlogn),43,练习,1.若需在O(nlog2n)的时间内完成对数组的排序，