JS 排序算法总结

前言

现在的前端对计算机基础要求越来越高了，排序和查找也是热门的算法面试题。本篇总结一下前端中的一些排序算法。如果有什么问题或建议，欢迎下方留言评论，共同探讨。

正文

Array.prototype.sort

原生 JS 自身的排序算法 sort()，有其本身的优缺点；

let arr = [1, 20, 10, 22, 11, 24, 100]

console.log(arr.sort())
// [1, 10, 100, 11, 20, 22, 24]
console.log(arr.sort((a, b) => a - b))
// [1, 10, 11, 20, 22, 24, 100]

直接调用会将元素转化成字符串进行排序；可通过传入内部函数来实现升序或排序，内部算法同样是快速排序，在实现上肯定是比我们所使用的快速排序复杂的多，主要是做了性能上的优化。所以，我们可以放心的使用 Array.prototype.sort() 进行排序。

冒泡排序（Bubble Sort）

原理：如名字一般，泡泡越往上越大，循环遍历，每次循环找出一个最大值往最后放；

思路：如图，每次循环能找出一个最大值，每次循环里得比较所有剩余元素，所以需要嵌套循环，一次为比较的轮数（arr.length - 1），一次为每轮的比较次数 (arr.length - 1 - i 已经比较的轮数)；每次比较前元素比后元素大则交换位置；

性能：

时间复杂度：平均时间复杂度是 O(n^2)
空间复杂度：由于辅助空间为常数，所以空间复杂度是 O(1)

代码：

function bubbleSort(arr) {
  let temp = 0
  // 比较的轮数
  for (let i = 0; i < arr.length - 1; i++) {
    // 每轮比较的次数
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 前后元素对比，大则交换位置
      if (arr[j] > arr[j + 1]) {
        temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}

插入排序（Insert Sort）

原理：构建有序数列，对未排序元素，在有序数列中的元素从后向前扫描（正向亦可），找到位置并插入；（原理如抽牌一般，抽牌与手中的牌比较，找到位置插入）

思路：嵌套循环，外循环遍历未排序数组，里循环遍历有序数组，未排序元素与有序数组元素从后往前比较，比有序元素大则往后插入，并跳出内循环，继续比较未排序元素；

性能：

时间复杂度：平均算法复杂度为 O(n^2)
空间复杂度：辅助空间为常数，空间复杂度是 O(1)

代码：

function insertSort(arr) {
  let res = [] // 有序数组
  res.push(arr[0]) // 放入第一个元素
  // 外循环遍历未排序数组
  for (let i = 1; i < arr.length; i++) {
    // 内循环遍历有序数组
    for (let j = res.length - 1; j >= 0; j--) {
      // 原数组元素比新数组元素大，往后插入元素，并跳出内循环
      if (arr[i] > res[j]) {
        res.splice(j + 1, 0, arr[i])
        break
      }
      // 循环到头，未排序元素都比有序元素小，则在头部插入元素
      if (j === 0) {
        res.unshift(arr[i])
      }
    }
  }
  return res
}

快速排序（Quick Sort）

原理：快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的 2 个子序列，然后递归地排序两个子序列。

思路：挑选一个元素作为基准值，循环遍历整个数组，每个元素与基准值比较，分为两个数组，此时递归这两个数组，直到数组中的元素个数小于等于一个，则返回该数组，组合所有数组和基准值及得到有序数组；

性能：

时间复杂度：平均时间复杂度 O(nlogn)
空间复杂度：辅助空间是 logn，所以空间复杂度为 O(logn)

代码：

function quickSort(arr) {
  // 当数组元素个数小于等于一个时结束递归
  if (arr.length <= 1) {
    return arr
  }
  let arrLeft = []
  let arrRight = []
  let middleIndex = Math.floor(arr.length / 2) // 基准值这里取中间项
  let middleValue = arr.splice(middleIndex, 1)[0] // 获取元素，并删除原数组的该元素
  // 遍历整个数组，比较放入两个数组中
  for (let i = 0; i < arr.length; i++) {
    arr[i] < middleValue ? arrLeft.push(arr[i]) : arrRight.push(arr[i])
  }
  // 将两个数组递归调用，并组合数组
  return [...quickSort(arrLeft), middleValue, ...quickSort(arrRight)]

  // 组合数组用到了 ES6 中的解构赋值，也可使用 Array.prototype.concat 组合数组，如下
  // return quickSort(arrLeft).concat(middleValue, quickSort(arrRight))
}

待更新

排序算法还有很多，归并排序、希尔排序等等，后续再总结更新；