排序算法之--归并排序法

2020-12-13 16:24

阅读：265

标签：sort cheng length com bottom logs floor 位置 cat

归并排序法

参考文章：

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）

申请空间merge，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
设定两个指针p1和p2，最初位置分别为两个已经排序序列的起始位置left[0], right[0]。
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
- 如果是序列是数组结构，也可以不动指针，而是进行删除操作。即每次比较后，把被移动第一个元素的那个数组，使用shift方法删除被移动的第一个元素，然后继续这比较，left[0] right[0]。但是??，数组删除第一个元素导致它从新分配指针给每个数组元素，需要花费时间。所以还是使用移动指针的方法好??。
- 被移动指针的序列，是那个有相对较小的元素的序列。
重复步骤3直到其中一个指针到达序列尾。
将另一序列剩下的所有元素直接复制到合并序列merge的尾巴。

function merge(left, right){
  var result = [];
  //使用指针能提高速度。不使用shift方法，因为数组会重新分配指针，导致多花费时间。
  while(left.length > 0 && right.length > 0){
    if(left[0] ]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }
  return result.concat(left, right);
}

function mergeSort(arr){
  if(arr.length 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));
}