冒泡排序

定义

冒泡排序是一种简单的排序算法，它重复地遍历数组，比较相邻元素并在它们的顺序错误时交换它们。对数组的遍历重复进行，直到数组排序完成。

实现

• 声明一个变量 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; 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]

复杂度

该算法的平均时间复杂度为 O(n^2)，其中 n 是输入数组的大小。