算法 之 分治 - 合并排序-合并两个已排序的表
假定有一个数组 A[1...n]，low, middle, high 为它的三个索引，并有 1?≤ low?≤ middle < high?≤?n，使得两个子数组 A[low...middle]，A[middle+1...high] 各自按升序排列。
我们要重新排列A中元素的位置，使得 A[low...high] 中的元素也按升序排列。这就是合并 A[low...middle] 和 A[middle+1...high] 的过程。
?
举个例子，就是我们有个数组 A = { 0, 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 }; 这里 low=0, middle=5, high=10
我们要对它进行排序使 A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
?
我们可以使用这样的方法来合并这两个子数组：
首先使用两个索引 s 和 t，初始化时各自指向 A[low] 和 A[middle+1]，再用一个空数组 B[low...high] 做暂存器。每一次比较元素 A[s] 和 A[t]，将小的元素添加到辅助数组 B，如果相同就把 A[s] 添加进去。
然后更新索引，如果 A[s] ≤ A[t]，则 s 加 1，否则 t 加 1，当条件 s=middle+1 或 t=high+1 成立时过程结束。
s=middle+1 时，我们把数组 A[t...high] 中剩余的元素添加到 B，
t=high+1 时，把数组 A[s...middle] 中剩余的元素添加到 B。
最后，把数组 B[low...high] 复制回 A[low...high]。
?
过程 ?Merge
输入 ?数组 A[1...n] 和它的三个索引 low, middle, high, 1 ≤ low?≤ middle < high?≤ n，
?? ? ? ? ?两个子数组 A[low...middle] 和 A[middle+1...high] 各自按升序排列
输出 ?合并两个子数组 A[low...middle] 和 A[middle+1...high] 的数组 A[low...high]
?
算法描述
comment: B[low...high] 是个辅助数组
s ← low; t ← middle+1; index ← low
while s?≤ middle and t?≤ high
?? ?if A[s]?≤ A[t] then
?? ? ? ?B[k] ← A[s]
?? ? ? ?s ← s + 1
?? ?else
?? ? ? ?B[k] ← A[t]
?? ? ? ?t ← t + 1
?? ?end if
?? ?index ← index + 1
end while
if s = middle+1 then B[k...high] ← A[t...high]
else B[k...high] ← A[s...middle]
end if
A[low...high] ← B[low...high]
?
以下是此算法的 Java 实现：
private static void merge(int[] array, int low, int middle, int high){int length = high - low + 1;int indexLowToMiddle = low;// 从 low 位置开始的索引int indexMiddleToHigh = middle + 1;// 从 middle+1 位置开始的索引int[] tempArray = new int[length];int tempIndex = 0;while (indexLowToMiddle <= middle && indexMiddleToHigh <= high){if (array[indexLowToMiddle] <= array[indexMiddleToHigh]){tempArray[tempIndex] = array[indexLowToMiddle];indexLowToMiddle += 1;}else{tempArray[tempIndex] = array[indexMiddleToHigh];indexMiddleToHigh += 1;}tempIndex += 1;}if (indexLowToMiddle == middle + 1){System.arraycopy(array, indexMiddleToHigh, tempArray, tempIndex, length - tempIndex);}else{System.arraycopy(array, indexLowToMiddle, tempArray, tempIndex, length - tempIndex);}System.arraycopy(tempArray, 0, array, low, length);}?