JavaScript 中的冒泡排序

概念 1

概念 2

运行时

冒泡排序是最受广泛讨论的算法之一，仅仅是因为它对数组排序效率低下。如果数组已经排序，冒泡排序只会遍历该数组一次（使用下面的概念二），然而最坏的情况是运行时间为 O(N²)，效率极低。

甚至前总统巴拉克·奥巴马也承认冒泡排序的低效率。

当我们绘制 O(N²) 的增长率时，我们发现，与其他排序算法（如归并排序，O(N Log N)）相比，它的增长速度要快得多。

鉴于冒泡排序的残酷性，理解该算法并解释其为何如此糟糕仍然很重要。

让我们深入研究一下冒泡排序编码的两个概念。

概念 1

• 遍历数组并检查每个元素是否与数组中的下一个元素相同。
• 如果当前元素大于下一个元素，则交换它们。
• 如果不大于，则向上移动指针并比较接下来的两个元素。
• 一旦到达数组的末尾，我们就知道最大的元素位于最后一个位置。
• 重复此过程 N 次，其中 N 是数组的长度，每次迭代到最后排序的元素。

概念 1 的可视化

让我们看一下如何在长度为 6 的数组上运行它。

概念 1 代码

我们需要两个指针（两个嵌套循环）来表示概念一。每次迭代时，上界都会减一，因为我们知道这个索引包含一个已排序的值。

function bubbleSortConcept1(arr) {
  for (let j = arr.length - 1; j > 0; j--) {
    for (let i = 0; i < j; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

概念 2

• 遍历数组并检查每个元素是否与数组中的下一个元素相同。
• 如果当前元素大于下一个元素，则交换它们。
• 表示交换已经发生。
• 如果发生交换，则再次循环遍历数组。
• 当没有发生交换时，我们知道数组是排序的。

概念 2 代码

此方法只需要一个指针，因为我们使用一个变量来存储布尔值，用于指示是否发生了交换。与概念一不同，此概念要求我们每次遍历数组中的每个元素时都要对其进行迭代。

function bubbleSortConcept2(arr) {
  let swapped;

  do {
    swapped = false;
    console.log(arr);
    arr.forEach((item, index) => {
      if (item > arr[index + 1]) {
        // Save the value to a variable so we don't lose it
        let temp = item;
        arr[index] = arr[index + 1];
        arr[index + 1] = temp;
        swapped = true;
      }
    })
  } while (swapped);
}

运行时

冒泡排序是最低效的排序算法之一，复杂度为 O(N²)。最坏的情况下，我们必须将数组中的每个元素与其他所有元素进行比较，因此复杂度为 O(N²)。