排序算法之归并排序

文章目录

1. 1. 归并排序
   1. 1.1. 规则
   2. 1.2. 时间复杂度
   3. 1.3. 优缺点
2. 2. 算法实现
   1. 2.1. js代码
   2. 2.2. 分析
3. 3. 参考文档

归并排序（Merge-Sort），是使用了分治法的一个典型应用。将已有序的子数组合并，得到一个有序数列，即先递归地将它们分成两半分别排序，然后将结果合并起来。

归并排序

归并排序是分治法的一个典型应用，将问题分解成几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后在合并这些子问题的解来建立原问题的解。

实现归并的一种最直接的方法是将两个要归并的有序数组，归并到第三个数组中。所以它需要额外的空间来实现归并。

规则

首先，申请空间，用来存放归并后的数组；
然后，设定两个指针，指向待归并数组的起始位置；
比较元素，选择较小的元素放入合并空间中，并将指针移到下一位置；
依次比较，直到指针超出数组末尾，把余下的所有元素归并到合并序列的末尾。

时间复杂度

归并排序对于任意长度为 N 的数组，排序所需时间和 NlogN成正比。
比较操作的次数介于 NlgN／2 和 NlgN-N+1。
赋值操作的次数是 2NlgN。
空间复杂度为 O(n)。

优缺点

1. 归并排序的空间复杂度不是最优的，他需要额外空间来存放已排序序列。

2. 归并排序可以减少比较次数，剩余元素不进行比较也可将其数据排序。

3. 归并排序是一种渐进最优的基于比较排序的算法，也就是说，在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是 NlgN。

算法实现

js代码

merge_sort.js

function merge_sort(arr) {
  if(arr.length == 1) {
	return arr;
  };

  var middle = Math.floor(arr.length/2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(merge_sort(left), merge_sort(right));
};

function merge(left, right) {
  var result = [];
  while(left.length > 0 && right.length > 0) {
    if(left[0] < right[0]) {
        result.push(left.shift());
    } else {
        result.push(right.shift());
    };
  };
  return result.concat(left).concat(right);
};

分析

我们来看一下打印日志后的交换过程：

其实归并排序很好理解，运用分治思想，把一个数组先分成左右两个数组，再把左右两个数组分别再拆分成两个数组，直到左右两个数组只有一个元素。然后逐步依次比较归并，最后归并成一个完整的有序数组。

看下图更详细的展示归并排序的操作：

有一个很好的比喻来描述归并排序，就是假如桌子上放着两摞倒扣的扑克牌，这两摞扑克牌都是已经依序从上到下排列好的，那你要如何才能将两摞扑克牌合成有序的一副扑克牌呢？条件是每次只能拿起任意一摞扑克牌的最上面的一张。

很简单，我们把两摞扑克牌分别命名为 A 和 B，这样方便讲解。分别翻开两摞拍的第一张 A1 和 B1，比较两个的大小，如果 A1 < B1 则把 A1 倒扣放到一边。接下来拿起 A2 与 B1 做比较，如果 A2 > B1 则把 B1 倒扣放到刚才放到一边的 A1 上面。重复这个过程，直到 A 或 B 任意一摞拿空，把剩下的拍依次倒扣放到已排好的那摞扑克牌上面。这样我们就把两摞扑克牌有序的合并为一摞了。

参考文档

• 图灵程序设计丛书–算法(第4版)
• 算法导论(原书第三版)
• 归并排序·源代码

---