归并排序

[myLightLin]

常见算法对比

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O（n²）	√
快排、归并	O（nlogn）	√
桶、计数、基数	O（n）	×

简介

归并排序，先递归，把数据从中间切成两部分，然后对这两部分进行排序，最后再将排序好的各个部分合并起来，数据就变有序了。

代码

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

function merge(left, right) {
  let temp = []
  let leftIndex = 0
  let rightIndex = 0
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      temp.push(left[leftIndex])
      leftIndex++
    } else {
      temp.push(right[rightIndex])
      rightIndex++
    }
  }
  return temp.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}

const arr = [11, 8, 3, 9, 7, 1, 2, 5]
mergeSort(arr)  // [1, 2, 3, 5, 7, 8, 9, 11]

动画演示

总结

1. 归并排序时间复杂度 O（nlogn），空间复杂度是 O（n）,排序过程是稳定的。
2. 相比快速排序，它是自下而上处理的。