算法介绍
归并排序(Merge Sort)是利用分治的思想实现的一种稳定的排序方法，该算法采用经典的分治(divide-and-conquer)策略，分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案合并在一起，即分而治之。
算法描述
一、分(Divide)：将N个元素分成两个含N/2个元素的子序列。
二、治(Conquer)：用合并排序法对两个子序列递归的排序。
三、合(Combine)：合并两个已排序的子序列以得到排序结果。
动图演示
算法分析
时间复杂度：O(NlogN)
空间复杂度：O(N)
稳定性：稳定
归并排序以O(NlogN)的最坏时间复杂度运行，而使用的比较次数几乎是最优的。算法中最基本的操作是合并两个已排序的表，合并的时间很显然是线性的。合并时使用了两个辅助数组的额外空间，并且为了合并的方便设置哨兵。
虽然归并排序的运行时间是O(NlogN)，但是它有一个明显的问题，即合并两个已排序数组的时候用到线性附加内存，数据的多次拷贝明显减慢了排序速度，因此较少使用归并排序算法进行内部排序。
归并排序与其他O(NlogN)的排序算法比较，归并排序的运行时间严重依赖于比较元素和在数组(以及临时数组)中移动元素的相对开销。值得一提的是，这些开销是与语言相关的。
例如，在Java中，进行一次元素比较可能是昂贵的(因为比较可能不容易被内嵌，从而动态调度的开销可能会减慢执行速度)，但是移动元素则是省时的(因为它们是引用的赋值，而不是庞大对象的拷贝)。归并排序使用所有流行的排序算法中最少的比较次数，因此是使用Java的通用排序算法中的上好的选择。事实上，它就是标准Java类库中泛型排序所使用的算法。
在C++的泛型排序中，如果对象庞大，那么拷贝对象可能需要很大的开销，而由于编译器具有主动执行内嵌优化的能力，因此比较对象常常是相对省时的。在这种情况下，如果我们还能够使用更少的数据移动，那么有理由让一个算法多使用一些比较。快速排序则达到了这种平衡，并且是C++库中通常所使用的排序算法。在Java中，快速排序也用作基本类型的标准库排序。
代码实现
// C++ void mergeSort(int a[], int length, int left, int right) { // 归并排序(递归版)，启动时left = 0，right = length- 1 int mid = left + (right - left) / 2; // 中间(分割)位置 if (left < right) { // 递归出口 mergeSort(a, length, left, mid); // 递归排序左序列 mergeSort(a, length, mid + 1, right); // 递归排序右序列 merge(a, left, mid, right); // 合并左右子序列 } } void merge(int a[], int left, int mid, int right) { // 合并左右子序列 int n1 = mid - left + 1; // 左序列元素个数 int n2 = right - mid; // 右序列元素个数 int L[n1 + 1]; // 左辅助数组 int R[n2 + 1]; // 右辅助数组 for (int i = 0; i < n1; i++) { // 初始化左辅助数组 L[i] = a[left + i]; } for (int i = 0; i < n2; i++) { // 初始化右辅助数组 R[i] = a[mid + i + 1]; } // 哨兵，用于合并时的边界判断 const int INF = 0x7fffffff; // 32字节int最大值 L[n1] = INF; // 以无穷大(32字节int最大值)为数组结束标志 R[n2] = INF; // 以无穷大(32字节int最大值)为数组结束标志 int i = 0; // L数组指针 int j = 0; // R数组指针 for (int k = left; k <= right; k++) { // 每次选取两数组中较小者 if (L[i] <= R[j]) { // L[i] <= R[j] a[k] = L[i]; // L[i]填入 i++; // L数组指针后移 } else { // L[i] > R[j] a[k] = R[j]; // R[j]填入 j++; // R数组指针后移 } } }
// Java class MergeSort { // 归并排序驱动程序1(全排序) public void mergeSort(int[] array) { mergesort(array, 0, array.length - 1); // 调用私有方法排序 } // 归并排序驱动程序2(部分排序) public void mergeSort(int[] array, int left, int right) { mergesort(array, left, right); // 调用私有方法排序 } private void mergesort(int[] array, int left, int right) { if (left < right) { // 递归出口 int mid = left + (right - left) / 2; // 中间(分割)位置 mergesort(array, left, mid); // 递归排序左序列 mergesort(array, mid + 1, right); // 递归排序右序列 merge(array, left, mid, right); // 合并左右子序列 } } // 合并左右子序列 private void merge(int[] array, int left, int mid, int right) { int leftlength = mid - left + 1; // 左序列元素个数 int rightlength = right - mid; // 右序列元素个数 int[] arrayL = new int[leftlength + 1]; // 左辅助数组 int[] arrayR = new int[rightlength + 1]; // 右辅助数组 for (int i = 0; i < leftlength; ++i) { // 初始化左辅助数组 arrayL[i] = array[left + i]; } arrayL[leftlength] = Integer.MAX_VALUE;// 哨兵，用于合并时的边界判断 for (int i = 0; i < rightlength; ++i) { // 初始化右辅助数组 arrayR[i] = array[mid + i + 1]; } arrayR[rightlength] = Integer.MAX_VALUE;// 哨兵，用于合并时的边界判断 int i = 0; // L数组指针 int j = 0; // R数组指针 for (int k = left; k <= right; ++k) { // 每次选取两数组中较小者 if (arrayL[i] <= arrayR[j]) { array[k] = arrayL[i++]; // 填入较小者，指针后移 } else { array[k] = arrayR[j++]; // 填入较小者，指针后移 } } } }
参考
算法导论
数据结构与算法分析(Java语言描述)
数据结构(C语言版)
————————————————
版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
