JavaScript 之冒泡排序

Question

冒泡排序，是一个相对较为简单易于理解的排序算法。下面以升序为例。

原理

• 比较相邻的两个元素a、b。若 a > b，则互换 a 与 b 的位置，否则不变。
• 按照上面的规则，第一轮循环次数为 array.length - 1，一轮循环结束，数组最后一项应该是最大数。
• 第二轮开始，循环次数为 array.length - 1 - 1，同样把本次循环的最大项互换到 array[length - 1 - 1] 的位置上。
• 以此类推...

图示

实现

// 冒泡排序（升序）
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

const array = [8, 12, 4, 0, 22, 8, 21, 3, 56]
console.log(bubbleSort(array)) // [0, 3, 4, 8, 8, 12, 21, 22, 56]

时间复杂度

可知冒泡排序执行次数是 (n-1) + (n-2) + ... + 2 + 1 = (n^2 - n)/2，根据 时间复杂度推导方式，可得到 O(n^2)。