算法 之 分治 - 合并排序-自底向上合并排序

这一次我们要介绍的是一种元素比较次数较少、比较有效的 自底向上合并排序算法。

假设要对这8个数字的数字排序：9, 4, 5, 2, 1, 7, 4, 6

考虑下面的这个排序方法

首先将输入元素分成4对（8个），合并每对为一个2元素的排序序列，然后将每两个连续的2元素的序列合并成大小为4的排序序列，最后将两个排序序列合并成途中所示的最终的排序序列。

我们这里设A为需要排序的n个元素的数组，首先合并?n/2?个连续元素对，生成大小为2的?n/2?排序序列，如果剩余一个元素，就让它进入下一轮迭代。

然后合并?n/4?个连续的2元素对的序列，生成?n/4?个大小为4的排序序列，如果剩余一个或者两个元素，就让它们进入下一轮迭代；如果剩余三个元素，将两个已排序的元素和另一个元素合并成一个3元素的排序序列。

继续这个过程，在第i次迭代中，合并?n/2i?对大小为2i-1的排序序列，生成大小为2i的?n/2i?个排序序列。如果有k个剩余元素（1 ≤ k ≤?2i-1），就将他们放在下一次合并中；如果有k个剩余元素（2i-1?< k <?2i），就将它们合并，形成一个大小为k的排序序列。

?

结合这张图也许你会理解得更加清楚

算法BottomUpSort 的思想实现了这张图的组合过程。

先用变量 mergeSize 存储被合并序列的大小，开始时将 mergeSize 置为1，每次执行外边的 while 循环时被乘以2。

low, middle, high 用来定义两个要排序的序列的边界（方便调用之前讲过的 Merge 算法）。

当 arrayLength 不是 mergeSize 的倍数时，实行步骤 [*]。这种情况下，如果剩余元素的数目比边界 middle 大，就要在大小为 MergeSize 的序列和剩余元素之间再进行一次排序。

?

过程 ?BottomUpSort

输入 ?n 个元素的数组 A[1...n]

输出 ?按非降序排列的数组 A[1...n]

?

算法描述

mergeSize ← 1

while mergeSize < n

?? ?low ← 0; ?middle ←?low + mergeSize - 1; high ←?low + mergeSize × 2 - 1

?? ?while high < n

?? ? ? ?Merge(A, low, middle, high)

?? ? ? ?low ← high + 1

?? ?end while

?? ?if middle < n then Merge(A, low, middle, n - 1) ? ? ? ?← 步骤 [*]

?? ?mergeSize ← mergeSize × 2

end while

?

算法中用到的 Merge 方法，可以参考：算法之 分治 - 合并排序-合并两个已排序的表

?

此算法的 Java 实现如下所示：

public static void buttomUpSort(int[] array){int arrayLength = array.length;int mergeSize = 1;while (mergeSize < arrayLength){int low = 0, middle = 0, high = 0;while (low + mergeSize * 2 - 1 < arrayLength){middle = low + mergeSize - 1;high = low + mergeSize * 2 - 1;merge(array, low, middle, high);low = high + 1;}middle = low + mergeSize - 1;if (middle < arrayLength - 1){merge(array, low, middle, arrayLength - 1);}mergeSize *= 2;}}