排序算法

冒泡排序

1. 从n项数组的第一项开始，两两比较，如果前一项比后一项大就交换位置。
2. 继续往后两两比较，重复第1步，直到比较到最后两项。至此，第一轮冒泡结束，最后一项一定是最大的，也就是最后一项已经被排序好了。
3. 第一轮冒泡结束后，开始第二轮，重复1,2步，直到比较到n-1项。
4. 重复第3步，直到完成所有轮冒泡。

[5, 4, 3, 2, 1]
[4, `5`, 3, 2, 1] -> [4, 3, `5`, 2, 1] -> [4, 3, 2, `5`, 1] -> [4, 3, 2, 1, `5`] // 第1轮
[3, `4`, 2, 1, 5] -> [3, 2, `4`, 1, 5] -> [3, 2, 1, `4`, 5] // 第2轮
[2, `3`, 1, 4, 5] -> [2, 1, `3`, 4, 5] // 第3轮
[1, `2`, 3, 4, 5] // 第4轮

以上面n = 5为例，总共需要进行4 + 3 + 2 + 1（即(n - 1) + (n - 2) + ... + 1）次排序，时间复杂度为O(n²)

当然最好的情况比如[1, 2, 3, 4, 5]，只需要进行n - 1次排序即可，时间复杂度为O(n)

function bubbleSort(array) {
  // 两层循环实现两两比较
  for (let i = 0; i < array.length; i++) {
    // 内层循环需要遍历到倒数第2位，这样 j + 1 是倒数第1位，正好比较到末尾
    // 另外已经比较完的数字就没必要再比较了，外层的i就代表比较完了几轮，要减去i
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // 交换比较的两项的位置
        [array[j], array[j + 1]] = [array[j + 1], array[j]]
      }
    }
  }
  return array
}