归并排序
什么是归并排序？
归并排序（Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
这里面提到了两个概念，分别是分治（法）和递归，它们是什么呢？
分治法
分治法（Divide and Conquer）是基于多路分支递归求和的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法中的快速排序和归并排序，傅立叶变换中的快速傅立叶变换…
分治模式在每层递归时都有三个步骤：
- 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
- 解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
- 合并这些子问题的解成原问题的解。
递归
递归（英語：Recursion），又译为递回， 在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况，如函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。 例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。 也可以理解为自我复制的过程。
归并排序的过程
归并排序算法完全遵循分治模式，直观上，其操作步骤如下：
- 分解：分解待排序的 n 个元素的序列成各具有 n/2 个元素的两个子序列。
- 解决：使用归并排序递归地排序两个子序列。
- 合并：合并两个已排序的子序列以产生已排序的答案。
当待排序的序列长度为 1 时，递归“开始回升”，在这种情况下无须作任何工作，因为长度为 1 的每个序列都已排好序。
分治法的伪代码
MERGE(A,p,q,r)
1 m = q-p+1
2 n = r-q
3 let L[1..m+1] and R[1..n+1] be new arrays
4 for i = 1 to m
5 L[i] = A[p+i-1]
6 for j = 1 to n
7 R[j] = A[q + j]
8 L[m + 1] = ∞
9 L[n + 1] = ∞
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i]<= R[j]
14 A[k] = L[i]
15 i = i + 1
16 else A[k] = R[j]
17 j = j + 1
MERGE 的详细工作过程如下：
-
第 1 行计算子数组 A[p..q] 的长度 n1；
-
第 2 行计算子数组 A[q+1..r] 的长度 n2；
-
第 3 行，创建长度分别为 m+1 和 n+1 的数组 L 和 R，每个数组中额外的位置保存哨兵；
-
第 4～5 行的 for 循环将子数组 A[p..q] 复制到 L[1..m]；
-
第 6～7 行的 for 循环将子数组 A[q+1..r] 复制到 R[1..n]；
-
第 8～9 行将哨兵放在数组 L 和 R 的末尾；
-
第 10～17 行，通过维持循环以下不变式，执行 r-p+1 个基本步骤：
在开始第 12～17 行 for 循环的每次迭代时，子数组 A[p..k-1]按从小到大的顺序包含 L[1..m+1] 和R[1..n+1] 中的 k-p 个最小元素。进而，L[i] 和 R[j] 是各自所在数组中未被复制回数组 A 的最小元素。
****使用循环不变式来理解算法的正确性****
我们必须证明第 12～17 行 for 循环的第一次迭代之前该循环不变式成立，且在该循环的每次迭代时保持该不变式，当循环终止时，该不变式须提供一种有用的性质来证明算法的正确性。
- 初始化：循环的第一次迭代之前，有 k=p，所以子数组 A[p..k-1] 为空。这个空的子数组包含 L 和 R 的 k-p=0 个最小元素。又因为 i=j=1，所以 L[i] 和 R[j] 都是各自所在数组中未被复制回数组 A 的最小元素。
- 保持：为了理解每次迭代都维持不变式，首先假设 L[i]≤R[j]。这时，L[i] 是未被复制回数组 A 的最小元素。因为 A[p..k-1]包含 k-p 个最小元素，所以在第 14 行将 L[i] 复制到 A[k] 之后，子数组 A[p..k] 将包含 k-p+1 个最小元素。增加 k 的值（在 for 循环中更新）和 i 的值（在第 15 行中），下次迭代重新建立该循环不变式。反之，若 L[i]>R[j]，则第 16～17 行会执行适当的操作来维持该循环不变式。
- 终止：终止时 k=r+1。根据循环不变式，子数组 A[p..k-1] 就是 A[p..r]，且按照从小到大的顺序排序，同时包含 L[1..m+1] 和 R[1..n+1] 中的 k-p=r-p+1 个最小元素。数组 L 和 R 一起包含 m+n+2=r-p+3 个元素。除了两个最大的元素外，其他所有元素都已被复制回数组 A，这两个最大的元素就是哨兵。
归并排序的伪代码
前面我们分析了分治算法的过程，我们可以把 MERGE 作为归并排序算法中的一个子程序来用。
MERGE-SORT(A,p,r)
1 if p < r
2 q = [(p+r)/2]
3 MERGE-SORT(A,p,q)
4 MERGE-SORT(A,q+1,r)
5 MERGE(A,p,q,r)
上面已经对分治法做了正确性证明，归并排序的正确性不言而喻。
归并排序的算法分析
分治算法运行时间的递归式来自基本模式的三个步骤，即分解、解决和合并。假设 T(n) 是规模为 n 的一个问题的运行时间。若问题规模足够小，如对某个常量 c，n≤c，则直接求解需要常量时间，可以将其写成 O(1)。假设把原问题分解成 a 个子问题，每个子问题的规模是原问题的 1/b。为了求解一个规模为 n/b 的子问题，需要 T(n/b) 的时间，所以需要 aT(n/b) 的时间来求解 a 个子问题。如果分解问题成子问题需要时间 D(n)，合并子问题的解成原问题的解需要时间 C(n)，那么得到递归式：
现在我们来讨论归并排序。假定问题规模是 2 的幂（不是 2 的幂时也能正确地工作），归并排序一个元素的时间是常量，当有 n>1 个元素时，分解运行的时间如下：
-
分解：分解步骤仅仅计算子数组的中间位置，需要常量时间，因此，
。
- 解决：递归地求解两个规模均为 n/2 的子问题，需要 2T(n/2) 的运行时间。
-
合并：在 MERGE 函数中，第 1～3 行和第 8~11 行中每行需要常量时间，第 4～7 行的 for 循环需要
（这里的 n 指数据规模）的时间，并且，第 12～17 的 for 循环有 n 次循环，每次迭代需要常量时间。因此，对于归并排序，
。
为了分析归并排序，我们可以将 D(n) 与 C(n) 相加，即把一个 函数与另一个
函数相加，得到的和是一个 n 的线性函数，即
。把它与来自“解决”步骤的项 2T(n/2) 相加，将给出归并排序的最坏情况的运行时间
将递归式重写，得到
其中，常量 c 代表求解规模为 1 的问题所需要的时间以及在分解步骤与合并步骤处理每个数组元素所需要的时间。(相同的常量一般不可能刚好即代表求解规模为 1 的问题的时间又代表分解步骤与合并步骤处理每个数组元素的时间。通过假设 c 为这两个时间的较大者并认为我们的递归式将给出运行时间的一个上界，或者通过假设 c 为这两个时间的较小者并认为我们的递归式将给出运行时间的下界，我们可以暂时回避这个问题。两个界的阶都是 ，合在一起将给出运行时间为
)。
求解递归式的过程如下图所示：
可以看出，树根 cn 通过递归分解，直到规模降为 1 后，每个子问题只要代价 c。分解步骤一共经历了 次，即树高为
层，每层的代价为 cn，因此总代价为
。
算法复杂度
上面我们已经知道了，总代价为 ，忽略低阶项和常量 c，归并排序的时间复杂度为 O(nlogn)。
归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，但是这个申请额外的内存空间，会在合并完成之后释放，因此，在任意时刻，只会有一个临时的内存空间在使用，临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
代码实现
Javascript 递归版
function merge(left, right){
var result = [];
while(left.length > 0 && right.length > 0){
if(left[0] < right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left, right);
}
function mergeSort(arr){
if(arr.length <=1) return arr;
var middle = Math.floor(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
Go
迭代版
func MergeSort(list []int) []int {
var length = len(list)
if length < 2 {
return list
}
var mid = length / 2
return merge(MergeSort(list[:mid]), MergeSort(list[mid:]))
}
func merge(x, y []int) []int {
var r []int = make([]int, len(x)+len(y))
for i, j := 0, 0; ; {
if i < len(x) && (j == len(y) || x[i] < y[j]) {
r[i+j] = x[i]
i++
} else if j < len(y) {
r[i+j] = y[j]
j++
} else {
break
}
}
return r
}
递归版
func merge(data []int) []int {
sum := len(data)
if sum <= 1 {
return data
}
left := data[0 : sum/2]
lSize := len(left)
if lSize >= 2 {
left = merge(left)
}
right := data[sum/2:]
rSize := len(right)
if rSize >= 2 {
right = merge(right)
}
j := 0
t := 0
arr := make([]int, sum)
fmt.Println(left, right, data)
for i := 0; i < sum; i++ {
if j < lSize && t < rSize {
if left[j] <= right[t] {
arr[i] = left[j]
j++
} else {
arr[i] = right[t]
t++
}
} else if j >= lSize{
arr[i] = right[t]
t++
} else if t >= rSize{
arr[i] = left[j]
j++
}
}
return arr
}
参考文献
- 《算法导论 第三版》
- 维基百科
