分治算法合并排序

A. 归并排序

归并排序 （Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

这里面提到了两个概念，分别是 分治（法） 和 递归 ，它们是什么呢？

分治法（Divide and Conquer）是基于多路分支递归求和的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多凯宏的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法中的快速排序和归并排序，傅立叶变换中的快速傅立叶变换…

分治模式在每层递归时都有三个步骤：

递归（英语：Recursion），又译为递回， 在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况，如函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。 例如，当两面镜子相互之间睁丛近似平行时，镜中嵌套的图像是以无限递归的形式出现的。 也可以理解为自我复制的过程。

归并排序算法完全遵循分治模式，直观上，其操作步骤如下：

当待排序的序列长度为 1 时，递归“开始回升”，在这种情况下无须作任何工作，因为长度为 1 的每个序列都已排好序。

MERGE 的详细工作过程如下：

我们必须证明第 12～17 行 for 循环的第一次迭代之前该循环不变式成立，且在该循环的每次迭代时保持该不变式，当循环终止时，该不变式须提供一种有用的性质来证明算法的正确性。

前面我们分析了分治算法的过程，我们可以把 MERGE 作为归并排序算法中的一个子程序来用。

上面已经对分治法做悉孙樱了正确性证明，归并排序的正确性不言而喻。

分治算法运行时间的递归式来自基本模式的三个步骤，即分解、解决和合并。假设 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 个元素时，分解运行的时间如下：

为了分析归并排序，我们可以将 D(n) 与 C(n) 相加，即把一个 函数与另一个 函数相加，得到的和是一个 n 的线性函数，即 。把它与来自“解决”步骤的项 2T(n/2) 相加，将给出归并排序的最坏情况的运行时间

将递归式重写，得到

其中，常量 c 代表求解规模为 1 的问题所需要的时间以及在分解步骤与合并步骤处理每个数组元素所需要的时间。(相同的常量一般不可能刚好即代表求解规模为 1 的问题的时间又代表分解步骤与合并步骤处理每个数组元素的时间。通过假设 c 为这两个时间的较大者并认为我们的递归式将给出运行时间的一个上界，或者通过假设 c 为这两个时间的较小者并认为我们的递归式将给出运行时间的下界，我们可以暂时回避这个问题。两个界的阶都是 ，合在一起将给出运行时间为 )。

求解递归式的过程如下图所示：

可以看出，树根 cn 通过递归分解，直到规模降为 1 后，每个子问题只要代价 c。分解步骤一共经历了 次，即树高为 层，每层的代价为 cn，因此总代价为 。

上面我们已经知道了，总代价为 ，忽略低阶项和常量 c，归并排序的时间复杂度为 O(nlogn)。

归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，但是这个申请额外的内存空间，会在合并完成之后释放，因此，在任意时刻，只会有一个临时的内存空间在使用，临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

Javascript 递归版

Go

迭代版

递归版

B. 归并排序算法是什么

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置。

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。

重复步骤3直到某一指针超出序列尾。

将另一序列剩下的所有元素直接复制到合并序列尾。

C. 什么是分治法的合并排序

分治法、是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
合并排序、是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
都是网络复制来的，别鄙视。以解决问题为根本原则。对你有帮助就好！

D. 分治算法几个经典例子

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础。

图二

大整数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循环赛日程表

汉诺塔