每日一算法：冒泡排序

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

工作原理

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

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

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

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

numbers swapped

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
      }
    }
    if (!swapped) return a
  }
  return a
}

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

此示例来自 30 seconds of code 的 bubbleSort