归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序以O(NlogN)最坏情形时间运行，所使用的比较次数几乎是最优的，同时也是递归算法的经典实例。该算法中的基本操作是合并两个已经排序好的序列。
首先关于递归的定义:
- 栈有一个重要应用是在程序设计语言中实现递归.一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称作递归函数
- 尾递归: 在函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
归并排序的基本定义:
假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列;再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序
归并排序的基本算法实现:
两个数组有序数组A、B以及空数组C(容量为AB之和或者大于AB之和)，定义三个计数器Actr、Bctr、Cctr(你也可以叫做指针)，他们初始位置都在对应数组的第一个元素位置。比较A[Actr]与B[Bctr]，将较小的数字放在C中，然后相关的计数器指针指向当前数组的下一个位置，当有一个数组比较完毕之后，拷贝另一个数组剩下的所有元素到C的末尾。
归并排序算法实现步骤:
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
归并排序动画教程和排序过程动画演示，在这里感谢老四的同事”菠菜”同学提供的视频演示，让我们更加清晰的了解合并排序的过程，抱拳。
归并排序的相关结构参数:
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n+logn)
- 效率: 占用内存，但却是效率高且稳定的算法
- 归并排序算法稳定性: 稳定排序(两两比较，不存在跳跃)
- 使用场景: Java中的Collections.sort方法使用的就是一种叫做TimeSort的增强型归并排序算法
归并排序的命名来自它的实现原理：把一系列排好序的子序列合并成一个大的完整有序序列。从理论上讲，这个算法很容易实现。我们需要两个排好序的子数组，然后通过比较数据大小，先从最小的数据开始插入，最后合并得到第三个数组。然而，在实际情况中，归并排序还有一些问题，当我们用这个算法对一个很大的数据集进行排序时，我们需要相当大的空间来合并存储两个子数组。就现在来讲，内存不那么昂贵，空间不是问题，因此值得我们去实现一下归并排序，比较它和其他排序算法的执行效率。
代码示例如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
package com.glorze.sort; import java.util.Arrays; /** * 归并排序算法的实现(使用递归) * @ClassName MergeSortWithRecursion * @author: glorze.com * @since: 2018年4月6日 下午6:46:00 */ public class MergeSortWithRecursion { /** * 返回排序后的结果 * @Title: mergeSortWithRecursion * @param arr * @return int[] * @author: 高老四博客 * @since: 2018年4月6日 下午6:46:40 */ public static int[] mergeSortWithRecursion(int arr[]) { return sort(arr， 0， arr.length - 1); } /** * 排序函数 * @Title: sort * @param arr * @param left * @param right * @return int[] * @author: 高老四博客 * @since: 2018年4月6日 下午6:50:10 */ public static int[] sort(int arr[]， int left， int right) { if (left >= right) { return arr; } // 中间索引 int center = (left + right) / 2; // 左半数组递归 sort(arr， left， center); // 右半数组递归 sort(arr， center + 1， right); // 递归后合并 return merge(arr， left， center， right); } /** * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序 * @Title: merge * @param arr 数组对象 * @param left 左数组的第一个元素的索引 * @param center 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 * @param right 右数组最后一个元素的索引 * @return int[] * @author: 高老四博客 * @since: 2018年4月6日 下午6:48:58 */ public static int[] merge(int[] arr， int left， int center， int right) { // 临时数组 int temp[] = new int[arr.length]; int mid = center + 1; // idx记录做数组第一个元素的索引 int idx = left; // 缓存左数组的第一个索引 int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出最小的放入临时数组 if (arr[left] <= arr[mid]) { temp[idx++] = arr[left++]; } else { temp[idx++] = arr[mid++]; } } // 剩余部分依次放入临时数组(两个while执行一个) while (mid <= right) { temp[idx++] = arr[mid++]; } while (left <= center) { temp[idx++] = arr[left++]; } // 拷贝回原数组 while (tmp <= right) { arr[tmp] = temp[tmp++]; } return arr; } public static void main(String[] args) { int arr[] = { 1， 3， 5， 7， 9， 2， 4， 6， 8 }; arr = MergeSortWithRecursion.mergeSortWithRecursion(arr); System.out.println("归并排序递归实现:" + Arrays.toString(arr)); } } |
我们知道，算法我们通常都需要找到更加完美、效率更高的方式，上述归并排序的代码大量的使用了递归，虽然代码看起来比较清晰易懂，但是大量的递归会造成时间和空间的上的性能损耗。如果我们追求排序的效率，可以将递归改为迭代，这样的话性能会进一步提高。为了文章排版，合并排序的动画演示过程在下方展示:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
package com.glorze.sort; import java.util.Arrays; /** * 迭代实现递归排序 * @ClassName MergeSortNoRecursion * @author: glorze.com * @since: 2018年4月6日 下午7:09:50 */ public class MergeSortNoRecursion { public static int[] mergeSortNoRecursion(int arr[]) { return mergeSort(arr， 0， arr.length - 1); } public static int[] mergeSort(int arr[]， int left， int right) { int temp[] = new int[arr.length]; int idx = 1; while (idx < arr.length) { mergePass(arr， temp， idx); idx += idx; mergePass(temp， arr， idx); idx += idx; } return arr; } public static void mergePass(int a[]， int b[]， int idx) { int i = 0; while (i <= a.length - 2 * idx) { // 两两归并 merge(a， b， i， i + idx - 1， i + 2 * idx - 1); i = i + 2 * idx; } // 归并最后两个数组 if (i + idx < a.length) { merge(a， b， i， i + idx - 1， a.length - 1); } else { // 若最后只剩下单个数组 for (int j = i; j < a.length; j++) { b[j] = a[j]; } } } public static void merge(int a[]， int b[]， int left， int mid， int right) { int i = left， j = mid + 1， k = left; while ((i <= mid) && (j <= right)) { if (a[i] < a[j]) { b[k++] = a[i++]; } else { b[k++] = a[j++]; } } if (i > mid) { for (int q = j; q <= right; q++) { b[k++] = a[q]; } } else { for (int q = i; q <= mid; q++) { b[k++] = a[q]; } } } public static void main(String[] args) { int arr[] = { 1， 3， 5， 7， 9， 2， 4， 6， 8 }; arr = MergeSortNoRecursion.mergeSortNoRecursion(arr); System.out.println("归并排序非递归实现:" + Arrays.toString(arr)); } } |
非递归的迭代方法，避免了递归时深度为log2n的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O(n)，并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。当然，你基本必须要做的是熟练掌握递归方式的情况之下了解迭代方式。
更博不易，如果觉得文章对你有帮助并且有能力的老铁烦请赞助盒烟钱，点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额，老四这里抱拳了。赞助时请备注姓名或者昵称，因为您的署名会出现在赞赏列表页面，您的赞赏钱财也会被用于小站的服务器运维上面，再次抱拳。
