这个冒泡排序的实现是错误的吗？

Question

不使用通常的 do-while 循环进行排序，如果我们使用 2 个 for 循环，可以吗？

let bubbleSort = (arr) => {
    console.log(arr);
    for(let i=0; i<arr.length; i++) {
        for (j=0; j<arr.length; j++) {
            if (arr[j] > arr[j+1]){
                console.log("swapped (i,j)->", arr[j],arr[j+1])   
                let temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;

            }
        }
    }

    return arr

}

这个 returns 是正确的排序数组，但它是否比 do-while 循环更好。两者都是 O(n^2) 时间复杂度。

Answer 1

所有循环类型 do、while 和 for 都是等效的。它们只是程序员的语法糖，最终在运行时归结为同一件事。

您在此处发布的大部分是正确的冒泡排序实现，但也有一些改进点：

错误：代码正在访问内部循环中的越界索引：由于 arr[j+1] 语句，迭代到 j < arr.length - 1 而不是 j < arr.length。对于越界数组访问，大多数语言会崩溃或表现出未定义的行为，但 JS 只是将值与 undefined 进行比较并继续。
潜在错误：内部循环在内部循环中创建了一个全局 j 变量（感谢 Kaiido 指出了这一点）。该变量的值将在该函数之外持续存在，并可能在程序的其他地方导致意外行为。使用 let 声明变量（如果不应重新分配变量，则使用 const ）以确保它们在块的本地范围内。
在外循环的第一次迭代之后，数组中最右边的元素位于其最终排序位置（因为它是数组中最大的元素）。在外循环的第二次迭代之后，数组的最后两个元素位于它们最终的排序位置。等等。因此，我们可以缩短内循环的迭代次数，如下：j < arr.length - 1 - i.
如果在任何迭代中都没有执行交换，我们可以中断——数组已经排序。

这些优化不会提高时间复杂度，正如您所说，它是 O(n²)，但它们值得考虑，因为类似的优化方法可以提供帮助加速现实世界的排序程序。

需要考虑的几个风格要点：

在运算符之间使用间距（除非它们在 [] 中）。
考虑使用 destructuring assignment 来避免在交换值时使用 temp 变量。正如评论中所指出的，由于每次交换创建数组对象的开销，这会导致性能下降，因此它应该在生产构建中编译出来（尽管冒泡排序无论如何都不适合生产）。
与分号和垂直空格保持一致。

这里有一个可能的重写：

const bubbleSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    let swapped = false;
    
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        swapped = true;
      }
    }
    
    if (!swapped) { break; }
  }

  return arr;
};

for (let i = 0; i < 10000; i++) {
  const arr = Array(100).fill().map(e => ~~(Math.random() * 30));
  const expected = JSON.stringify(arr.slice().sort((a, b) => a - b));
  const actual = JSON.stringify(bubbleSort(arr.slice()));
  
  if (actual !== expected) {
    throw new Error(`test failed: expected ${expected} but got ${actual}`);
  }
}

console.log("10000 tests passed");

有趣的后续练习：

使用递归写出没有循环的代码。
允许用户传递自定义比较器函数，类似于内置 Array#sort。这样，您可以对对象数组进行排序或指定排序顺序。
使用 console.time 将其与其他排序例程进行基准测试（感谢 Medet 的想法）。优化有多大帮助？考虑使用种子随机数进行测试。

这个冒泡排序的实现是错误的吗？

Is this implementation of bubble sort wrong?

javascript

sorting

bubble-sort