本节的两种排序算法：归并排序和快速排序都基于递归实现，平均时间复杂度都为 O(nlgn)

归并排序

归并思想：

数组分成两个子数组（通常从中间分）
子数组也继续分（递归）直到只有一个元素（终止条件）

归并排序还用到了合并两个有效数组的工具函数，基于“双指针法”实现

function mergeArr(arr1, arr2) { // 合并两个有序数组，返回一个新数组
  const len1 = arr1.length
  const len2 = arr2.length
  const res = []
  let i = 0 // 两个指针分别指到 arr1, arr2
  let j = 0
  while (i < len1 && j < len2) { // 两个数组都有值，按顺序填
    if (arr1[i] < arr2[j]) {
      res.push(arr1[i])
      i++
    } else {
      res.push(arr2[j])
      j++
    }
  }
  if (i < len1) {// arr2填完了，arr1还有
    return res.concat(arr1.slice(i))
  } else {
    return res.concat(arr2.slice(j))
  }
}

function mergeSort(arr) {
  const len = arr.length
  if (len <= 1) { // 递归边界条件，分到数组里只有一个元素
    return arr
  }
  const mid = Math.floor(len / 2)
  const sortedLeft = mergeSort(arr.slice(0, mid))
  const sortedRight = mergeSort(arr.slice(mid))// 省略第2个参数默认到数组末尾
  return    mergeArr(sortedLeft, sortedRight)
}

平均时间复杂度 O(nlgn)

快速排序

快排思想：

选择一个元素作为”基准”，通常取中间的元素。
所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
(递归)对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止(终止条件)。

参考：快排的js实现——阮一峰

function quickSort(arr){ 
  const len = arr.length
  if(len <= 1){ // 递归，先写边界条件
    return arr
  }
  const midIndex = Math.floor(len/2) // 确定基准元素
  const left = []
  const right = []
  for(let i=0; i<len;i++){
    if(i === midIndex){ // 跳过基准元素不处理
      continue
    }
    if(arr[i] < arr[midIndex]){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return [...quickSort(left), arr[midIndex], ...quickSort(right)]
}

这种实现没有操作原数组，而是返回一个新数组，空间复杂度较高 O(n)
平均时间复杂度 O(nlgn)

数据结构与算法

进阶排序算法——归并/快速

归并排序

快速排序