思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

image-20200324202429989.png

实现

/**
 * 
 * @param {*} array 排序的原始数组
 * @param {*} left 左边有序序列的初始索引
 * @param {*} mid 中间索引
 * @param {*} right 右边索引
 * @param {*} temp 做中转的数组
 */
function merge(array, left, mid, right, temp) {
  let i = left //左边有序序列的第一个索引
  let j = mid + 1//右边有序序列的第一个索引
  let t = 0 //temp的索引
  //1. 先把左右两边有序的数据按照规则填充到temp数组
  //直到左右两边的有序序列, 有一边处理完为止
  while (i <= mid && j <= right) {
    if (array[i] <= array[j]) {
      temp[t] = array[i]
      t++
      i++
    } else {
      temp[t] = array[j]
      t++
      j++
    }
  }
  //2. 把有剩余的一边的数据依次填充到temp后面
  while (i <= mid) {
    temp[t] = array[i]
    t++
    i++
  }
  while (j <= right) {
    temp[t] = array[j]
    t++
    j++
  }
  //3. 把temp数组拷贝给array
  //注意每次拷贝的长度不一定一样
  t = 0
  let tempLeft = left
  while (tempLeft <= right) {
    array[tempLeft] = temp[t]
    t++
    tempLeft++
  }
}
function mergeSort(array, left, right, temp) {//分解
  if (left < right) {
    let mid = Math.floor((left + right) / 2) //中间索引
    mergeSort(array, left, mid, temp)
    mergeSort(array, mid + 1, right, temp)
    //合并
    merge(array, left, mid, right, temp)
  }
}


let array = [8, 4, 5, 7, 1, 3, 6, 2]
let temp = new Array(array.length) //需要额外的空间
mergeSort(array, 0, array.length - 1, temp)
console.log(array);