算法 之 分治 - 合并排序-合并两个已排序的表

假定有一个数组 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);
}