归并排序法

参考文章:

https://www.cnblogs.com/chengxiao/p/6194356.html

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

基本思想:

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略。

分治法将问题(divide)成一些小的问题后求解,而治(conquer)的阶段则将分的阶段得到的各答案"集成"在一起,因此叫分而治之。

实现归并排序的2种方法:

递归法(Top-down) 

  1. 申请空间merge,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
  2. 设定两个指针p1和p2,最初位置分别为两个已经排序序列的起始位置left[0], right[0]。
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
    • 如果是序列是数组结构,也可以不动指针,而是进行删除操作。即每次比较后,把被移动第一个元素的那个数组,使用shift方法删除被移动的第一个元素,然后继续这比较,left[0] <=> right[0]。但是⚠️,数组删除第一个元素导致它从新分配指针给每个数组元素,需要花费时间。所以还是使用移动指针的方法好✌️。
    • 被移动指针的序列,是那个有相对较小的元素的序列。
  4. 重复步骤3直到其中一个指针到达序列尾。
  5. 将另一序列剩下的所有元素直接复制到合并序列merge的尾巴。
function merge(left, right){
  var result = [];
  //使用指针能提高速度。不使用shift方法,因为数组会重新分配指针,导致多花费时间。
  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, right);
}

function mergeSort(arr){
  if(arr.length <=1) return arr;
  var middle = Math.floor(arr.length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

ruby的实现:

 

迭代法(Bottom-up) 

原理如下(假设序列共有{\displaystyle n}个元素):

  1. 将序列每相邻两个数字进行归并操作,形成{\displaystyle ceil(n/2)}个序列,排序后每个序列包含两/一个元素
  2. 若此时序列数不是1个则将上述序列再次归并,形成{\displaystyle ceil(n/4)}个序列,每个序列包含四/三个元素
  3. 重复步骤2,直到所有元素排序完毕,即序列数为1
02-14 01:59