算法入门 - 归并排序

ES_her0

关注

发布于: 15 小时前

归并排序是一个比例厉害的算法，其指导思想很有用，创始人也很厉害。有一众博客在介绍怎么去实现，什么原理，唯独没有介绍发明人：冯诺依曼。计算机领域应该无人不知吧。算法思想算不上先进，甚至孙子兵法中都有提及：

故用兵之法，十则围之，五则攻之，倍则分之，敌则能战之，少则能逃之，不若则能避之。

以上来自《孙子兵法.谋攻篇》。其中提到就是分而治之，各个击破。归并排序就是使用这样的思想。所谓分治法是怎么分治的呢？

递归地把当前序列平均分割成两半（也可以不用递归）
保持元素顺序的同时将上一步得到的子序列集成到一起

通过下面这个动画，应该能很快了解到归并的过程：

在具体实现的时候，更详细的步骤如下：

将列表分割成单个元素
创建 2 个指针，一个指向左边的部分，一个指向右边，当较小的元素被取出时，指针才会移动。一直持续到每个指针都指向队尾

复杂度分析与应用

因为采取分治的思想，将一个列表从中间等分到不能再分割，这是个对数过程，所以首先肯定有 O(logn)。在指针相互比较大小时会遍历整个半区来寻找最小值，遇到遍历即使只遍历半个列表，严格的说是 O(n/2)，但我们会忽略常数，计作 O(N)。那么最终的复杂度便是 O(nlogn)。而且值得强调的是，归并排序的复杂度十分稳定，最好和最坏都是这个。JDk 中的 Arrays.sort()就是一种优化版的归并排序。

实现

注意边界的判断

public static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {	if (start >= end)		return;	int len = end - start, mid = (len >> 1) + start;	int start1 = start, end1 = mid;	int start2 = mid + 1, end2 = end;	merge_sort_recursive(arr, result, start1, end1);	merge_sort_recursive(arr, result, start2, end2);	int k = start;	while (start1 <= end1 && start2 <= end2)		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];	while (start1 <= end1)		result[k++] = arr[start1++];	while (start2 <= end2)		result[k++] = arr[start2++];	for (k = start; k <= end; k++)		arr[k] = result[k];}public static void merge_sort(int[] arr) {	int len = arr.length;	int[] result = new int[len];	merge_sort_recursive(arr, result, 0, len - 1);}

复制代码

发布于: 15 小时前阅读数: 4

ES_her0

关注

还未添加个人签名 2018.03.21 加入

还未添加个人简介

发布

暂无评论

创作场景

算法入门 - 归并排序

复杂度分析与应用

实现

ES_her0

评论