用最少的代码行实现 JavaScript 冒泡排序

我没拿到计算机科学学位，所以时不时会自学一些计算机科学概念。面试的时候有人问过我冒泡排序，所以我决定用 JavaScript 写一个实现。

冒泡排序的工作原理是什么？

简而言之，冒泡排序函数会遍历数组，将每个元素与其右侧相邻元素进行比较，如果相邻元素较小，则交换这两个元素。它会不断重复遍历数组，直到没有元素需要交换为止。

它看起来大概是这样的。

Start: [9,6,3,2,4]
After 1: [6,3,2,4,9]
After 2: [3,2,4,6,9]
After 3: [2,3,4,6,9]
After 4: [2,3,4,6,9]

为什么第三次之后顺序就正确了，却又重复了四次？

因为直到第四次运行后才知道订单是正确的，而且不需要进行任何交换。

所以我写了一个简单的函数。

function bubble(arr){
  do { 
    var swaps = false; 
    arr.forEach((val, ind) => {
      if (val > arr[ind + 1]) {
        swaps = true; 
        arr[ind] = arr[ind + 1];
        arr[ind + 1] = val;
      } 
    });
  } while (swaps == true);
  return arr;
}

这是最短的冒泡排序算法吗？

它成功了。但我希望确保用尽可能少的代码行实现它。当我用谷歌搜索“ javascript 最高效的冒泡排序”时，排名前两位的搜索结果都比我的多了 2-3 行代码。

归根结底，就是三件事：

1.他们使用for循环遍历数组，而我使用Array.prototype.forEach().

该forEach方法会将数组中该元素的值、索引，甚至数组本身都提供给对每个元素进行操作的回调函数。因此，我节省了一行代码。

当他们需要交换值时，他们必须声明一个临时值来保存其中一个值，但我已经将一个值作为参数传递给了该函数。

我的代码获取值和索引号（以 `value` 和 `index` 的形式val）ind：

if (val > arr[ind + 1]) { 
  swaps = true; 
  arr[ind] = arr[ind + 1]; 
  arr[ind + 1] = val;
}

他们的代码只获取索引号（如i）：

if (arr[i] > arr[i + 1]) { 
  swaps = true; 
  let temp = arr[i + 1]; 
  arr[i + 1] = arr[i]; 
  arr[i] = temp;
}

2.他们在创建循环之前还声明了一个变量来表示数组的长度for，而它forEach只是大概知道这一点。

3.其中一人在循环swaps外do... while使用关键字声明了一个布尔值let。我和另一人在循环内使用关键字声明了该布尔值var。let关键字的作用域是块级的，因此如果他们在循环内声明了变量，循环控制就无法访问它。关键字的作用域是函数级的，因此在声明和赋值之后，var循环内的任何位置都可以访问它。

使用let并没有显著提高可读性，反而增加了不必要的复杂性（在这种情况下）。

好吧，我的版本虽然短一些，但是它更好吗？

我对自己相当满意，但我已经知道使用forEach.

一旦开始循环，forEach就必须完成整个数组的循环。for循环可以使用 `exit`return或 ` breakexit` 关键字提前退出，也可以使用continue`end` 结束处理并跳到下一次迭代。该forEach方法没有这些功能。

循环的for优势在于，冒泡排序必须遍历所有值……几乎如此。

它不必将最后一个值与最后一个索引加一的未定义值进行比较。

可以将循环for设置为遍历除最后一个值之外的所有值，这意味着循环中的代码运行次数会减少一次。

获胜者：for循环。

另一个问题是确定数组长度的两种方法的相对效率。

其内部forEach基本上是运行一个for循环，并在每次迭代中查找数组长度。

在for循环变体中，数组长度被设置在一个变量中，然后循环使用该变量。

如果在循环过程中数组长度可能会发生变化，例如使用某个Array.prototype.splice方法删除重复项，那么在循环的每次迭代中查找数组长度就非常有用。

但是，如果数组大小保持不变，那么获取数组长度并将其存储在循环变量中以for供使用……似乎取决于引擎。在 V8（Chrome、node.js）中，查找速度似乎略快（根据Stack Overflow 上的讨论），但在其他引擎中，结果可能有所不同。

胜负：我们姑且称之为平局。

最后，关于声明let和赋值方式的var比较，实际上是一个比较简单粗暴的问题：声明一次 + 重复赋值是否比在一个语句中重复声明和赋值更快。

所以我对这两种方法进行了计时，在多个测试中分别运行了100亿次。var声明赋值法在每次测试中都以大约0.2%的优势胜出。这点差距不足以断定哪种方法更好。

胜者：我们也算平局吧。

所以，我的更好吗？

我的版本更短更易读，但能够在每次循环中跳过整个比较代码的执行，这无疑是循环的一大优势for。因此，哪个“更好”……嗯，这取决于你的优先级。