7.9 路归并排序★3◎4

7.9 路归并排序★3◎4

7.9 二路归并排序★3◎4

　　二路归并排序的基本思想：将两个有序表合并为一个有序表。
　　1个元素的表总是有序的，所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成 个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。
　　设r[u…t]由两个有序子表r[u，…，v-1]和r[v，…，t]组成，两个子表长度分别为v-u、t-v+1。合并方法为：

　　

　　对序列｛39，80，76，41，13，29，50，78，30，11，100，7｝进行二路归并排序的过程如下：
　　初始序列：39，80，76，41，13，29，50，78，30，11，100，7
　　第一趟归并：[39, 80],[41,76],[13,29],[50,78],[11,30],[7,100]
　　第二趟归并：[39,41,76,80], [13,29,50,78], [7,11,30,100]
　　第三趟归并：[13,29,39,41,50,76,78,80], [7,11,30,100]
　　第四趟归并：[7, 11, 13, 29, 30, 39, 41, 50, 76, 78, 80, 100]
　　【效率分析】
　　需要一个与表等长的辅助元素数组空间，所以空间复杂度为O(n)。
　　对n个元素的表，将这n个元素看做叶结点，若将两两归并生成的子表看做它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度减去1，即 ；每趟归并需移动记录n次，故时间复杂度为 。

7.9 路归并排序★3◎4