javascript - 为什么选择排序在 Javascript 中这么快？

Question

我正在为技术面试而学习，并且正在编写各种快速的 javascript 实现。大多数基本排序的随机数组基准测试结果是有道理的，但选择排序的速度快得惊人。我也不知道为什么。

这是我对选择排序的实现:

Array.prototype.selectionSort = function () {
  for (var target = 0; target < this.length - 1; target++) {
    var min = target;
    for (var j = target + 1; j < this.length - 1; j++) {
      if (this[min] > this[j]) {
        min = j;
      }
    }
    if (min !== target) {
      this.swap(min, target);
    }
  }
}

以下是具有 10000 个元素的同一随机生成数组的结果:
冒泡排序 => 148 毫秒
插入排序 => 94 毫秒
选择排序 => 91 毫秒
合并排序 => 45 毫秒

所有排序都使用相同的交换方法。那么为什么选择排序更快呢？我唯一的猜测是 Javascript 在数组遍历方面非常快，但在值突变方面很慢，因为 SelectionSort 使用最少的值突变，所以它更快。

** 供引用 **
这是我的冒泡排序实现

Array.prototype.bubbleSort = function () {
  for (var i = this.length - 1; i > 1; i--) {
    var swapped = false;
    for (var j = 0; j < i; j++) {
      if (this[j + 1] < this[j]) {
        this.swap(j, j+1);
        swapped = true;
      }
    }
    if ( ! swapped ) {
      return;
    }
  }
}

这是交换实现

Array.prototype.swap = function (index1, index2) {
  var val1 = this[index1],
      val2 = this[index2];
  this[index1] = val2;
  this[index2] = val1;
};

Answer 1

首先让我指出两个缺陷:

• 您的选择排序代码有问题。内循环需要是

  for (var j = target + 1; j < this.length; j++) {
  

  否则永远不会选择最后一个元素。

• 正如您所说，您的 jsperf 测试每次都会对“相同的随机生成的数组”进行排序。这意味着每个测试循环中的连续运行将尝试对已排序的数组进行排序，这将有利于像 bubblesort 这样具有线性最佳情况性能的算法。

  幸运的是，您的测试数组非常大，以至于 jsperf 一次只运行其测试循环的一次迭代，并在每次运行前调用初始化数组的设置代码。但是，这会困扰您较小的阵列。您需要在“定时代码”本身内部打乱数组。

---

Why is Selection Sort faster? My only guess is that Javascript is really fast at array traversal but slow at value mutation.

是的。写入总是比读取慢，并且对缓存值也有负面影响。

SelectionSort uses the least in value mutation

是的，这非常重要。选择排序和冒泡排序都有 O(n²) 运行时间，这意味着它们都执行大约 100000000 次循环条件检查、索引递增和两个数组元素的比较。

但是，虽然选择排序只进行 O(n) 次交换，但冒泡排序进行 O(n²) 次交换。这意味着不仅要改变数组，还要改变方法调用的开销。而且这比选择排序更频繁。这里有一些 example logs :

> swaps in .selectionSort() of 10000 element arrays
9989
9986
9992
9990
9987
9995
9989
9990
9988
9991
> swaps in .bubbleSort() of 10000 element arrays
24994720
25246566
24759007
24912175
24937357
25078458
24918266
24789670
25209063
24894328

糟糕。