冒泡排序

[myLightLin]

简介

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

冒泡排序就是每次比较相邻两个数，然后交换它们的位置，这样每一轮过后，最大的数就会去到最后位置，重复 n 次就完成了排序。

代码

function bubbleSort(arr) {
  const n = arr.length
  if (n <= 1) return
  
  for (let i = 0; i < n; i++) {
    let flag = false
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        swap(arr, j, j+1)
        flag = true
      }
    }
    if (!flag) break
  }
}

function swap(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

const arr = [4, 5, 6, 3, 9, 2]
bubbleSort(arr)  // [2, 3, 4, 5, 6, 9]

动画演示

总结

1. 冒泡排序平均时间复杂度为 O（n²），空间复杂度为 O（1）,排序过程是稳定的。
2. 最好情况下时间复杂度是 O（n）,最坏情况下数据是倒序，平均时间复杂度为 O（n²）。