每日一算法：冒泡排序.md

每日一算法：冒泡排序

冒泡排序是最糟糕的排序之一，但了解冒泡排序的工作原理对你来说很重要。主要原因是要理解它的功能，避免在代码中做任何与它有点相似的事情。

原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

JavaScript 实现

使用冒泡排序算法对数字数组进行排序。

• 声明一个变量 swapped，该变量指示在当前迭代期间是否交换了任何值。
• 使用扩展运算符（...）克隆原始数组 arr。
• 使用 for 循环遍历克隆数组的元素，在最后一个元素之前终止。
• 使用嵌套 for 循环在 0 和 i 之间的数组段上进行迭代，交换任何相邻的乱序元素，并将 swapped 设置为 true。
• 如果 swapped 在一次迭代后为 false，则不需要进行更多更改，因此将返回克隆的数组。

const bubbleSort = (arr) => {
  let swapped = false
  const a = [...arr]
  for (let i = 1; i < a.length - 1; i++) {
    swapped = false
    for (let j = 0; j < a.length - i; j++) {
      if (a[j + 1] < a[j]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }
    // swapped 表示如果某次循环中没有交换过元素，那么意味着排序已经完成
    if (!swapped) return a
  }
  return a
}

bubbleSort([2, 1, 4, 3]) // [1, 2, 3, 4]

此示例来自 30 seconds of code 的 bubbleSort

更多资料

• Bubble Sort
• Bubble Sort 可视化冒泡排序