javascript - 使用 for 循环的冒泡排序无法按预期工作

Question

我刚开始编写排序算法。目前我正在学习冒泡排序算法，我在网上找到了以下内容并且工作正常:

const arr = [3, 2, 6, 9, 3, 5];

const bubbleSort = array => {
  do {
    var isSorted = true;
    for (var i = 0; i < array.length; i++) {
      if (array[i] > array[i + 1]) {
        var temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        isSorted = false;
      }
    }
  } while(!isSorted)
  return array
};

输出:

[ 2, 3, 3, 5, 6, 9 ]

但是，当我尝试使用 if 语句而不是像下面这样的 while 循环来编写它时，它没有按预期工作:

const arr = [3, 2, 6, 9, 3, 5];

const bubbleSort = (array) => {
  let isSorted = false;
  if(!isSorted) {
    isSorted = true;
    for(var i = 0; i < array.length; i++) {
      if (array[i] > array[i + 1]) {
        var temp = array[i + 1];
        array[i + 1] = array[i];
        array[i] = temp;
        isSorted = false;
      }
    }
  }
  return array;
}

输出:

[ 2, 3, 6, 3, 5, 9 ]

我在这里做错了什么？

Answer 1

我们需要 while 循环来进行冒泡排序。

如果我们删除 while 那么我们将只在整个数组中“冒泡”一次。例如，如果

[3, 2, 6, 9, 3, 5];

这里 3(第一个元素)大于 2(第二个元素)所以我们交换它们，现在我们有

[2, 3, 6, 9, 3, 5]

当我们继续 for 循环时，我们接近较小的 3(第 6 个元素)，因此我们将它与 9(第 5 个元素)交换。并继续前进。

[2, 3, 6, 3, 9, 5]

从这里我们只会往上走，但我们可以分析情况。我们可以看到 3(第 4 个元素)小于 6(第 3 个元素)，但是 for 循环遥遥领先，所以我们不会遇到用更大的元素交换它的情况。所以我们必须从头开始再次“冒泡”，我们需要这样做，直到一切都排序为止。当没有任何东西可以交换时，就会发生这种情况，因为我们在交换时设置了 isSorted=false。数组排序后，我们将执行最后一次检查每个相邻对，如果它们全部排序，则不会发生交换，isSorted 将为 true

TLDR；我们需要 while 因为“冒泡”可能需要多次通过数组。