摘要：
此文介绍了归并排序的算法以及基本分析，最后总结。
此系列文均为方便日后重复粗略查看时不必翻看书籍。
由于该算法比较简单，所以直接给出算法导论中的算法伪代码。后续将着重算法分析。
算法过程
merge sort过程 ([2],P19)MERGE-SORT(A, p, r)
1 if p < r
2 then q ← ⌊(p + r)/2⌋
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
merge sort中用到的合并过程 ([2],P17)
MERGE(A, p, q, r)
1 n1 ← q - p + 1
2 n2 ← r - q
3 create arrays L[1 ‥ n1 + 1] and R[1 ‥ n2 + 1]
4 for i ← 1 to n1
5 do L[i] ← A[p + i - 1]
6 for j ← 1 to n2
7 do R[j] ← A[q + j]
8 L[n1 + 1] ← ∞
9 R[n2 + 1] ← ∞
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i] ≤ R[j]
14 then A[k] ← L[i]
15 i ← i + 1
16 else A[k] ← R[j]
17 j ← j + 1
算法分析
定理1.1将N个元素的数组排序，，归并排序使用N*lgN+O(N)次比较。（[1]，P4）证明：设C(N)为N个元素排序所用的比较次数。则排序前一半所用的比较次数为C( N/2)， 排序后一半所用的比较次数为C( （N+1)/2)。[除法结果小数点后面位数直接去掉]。合并的比较次数为N（对于两个子数组的每个元素都有一次比较）。下面关系式可以精确描述归并排序的比较次数：
C(N)=C(N/2) + C( (N+1)/2) +N (N>=2, C(1)=0) （1-1）
考虑N是2的幂时的情况,
C(2n) = C(2n-1)+C(2n-1)+2n=2C(2n-1)+ 2n
两边除以2n，我们发现
C(2n)/2n= C(2n-1)/ 2n-1 + 1 = C(2n-2)/ 2n-2 + 2 = C(2n-3)/ 2n-3 + 3 = … = = C(20)/ 20 + n = n
即： C(2n) = n*2n , ,这就证明了当N=2n ，C(N)=lg(N)*N ；
对于一般的N,定理可以通过式（1-1）归纳证明。[1]的第二章详细讨论了如何求解这样的递推关系。
TODO:添加[1]中chapter2对该定理一般的N的求解过程
式C(N)=C(N/2) + C( (N+1)/2) +N在[2]中的递归表示为：
![clip_image002[4]归并排序算法,算法-排序-归并排序(MergeSort)分析](/Files/20114/4cd7e75e-f139-4c6a-b5c3-3f4c28a6f5e1.gif)
（2.1）为了将和，将上述公式重写为：
![clip_image004[4]clip_image002[4]归并排序算法,算法-排序-归并排序(MergeSort)分析](/Files/20114/2dce58e8-0571-4be4-9f9a-66e22a122173.gif)
（2.2）C表示规模为1的问题所需的时间，即比较合并步骤中每个数组元素所需的时间。
注意：由于该表达式比较特殊（或者说相对简单），[2]在P22给出了一个形象的以树的方式将该公式进行了多重分解，最后得出总的代价为 clgn+cn,即：
![clip_image006[4]clip_image004[4]clip_image002[4]归并排序算法,算法-排序-归并排序(MergeSort)分析](/Files/20114/f225c2db-bb00-4ade-bc0d-91c04fe356f3.gif)
，此树形递归分解方法应该作为一种基本的sense印记在脑中。[2]中上述公式可以作为Chapter4中的主定理(Master Method)的一种情形来解决。
TODO:添加[2]主定理中该情形处理方式
总结
由上述公式(源于[1]和[2])及其处理过程，我们可以看出1. 此算法极其简单，非常合适算法入门中第一个介绍。[1],[2]基本上都是。
2. 此算法的算术表达方式极大的方便了对其复杂度的分析。算术表达式算法分析的根本。没有表达式，想破头也是非常困难的。
3. 运用一些形象的表示方法，也是可以处理一些简单的算术表达式的。如通过递归树的方式将[2]的公式最终解出复杂度。
4. 掌握一定的数学思考问题，解决问题方式是非常有必要的。
5. 平时要多注意数学素养，数学思维的运用。流水不腐、户枢不蠹。脑子越用越灵活。
参考文献：
[1]. 算法分析导论 Section1.2 计算复杂性,[2]. 算法导论,CH，V2， Section 2.3.1分治法
最新评论