为什么JavaScript实现的冒泡排序比其他排序算法快得多？

Question

我做了一些关于JavaScript排序算法性能比较的研究，发现了出乎意料的结果。冒泡排序提供了比其他算法如希尔排序、快速排序和原生JavaScript功能更好的性能。为什么会这样呢？也许我的性能测试方法有误？

你可以在这里找到我的研究结果。

以下是一些算法实现示例：

  /**
   * Bubble sort(optimized)
   */
  Array.prototype.bubbleSort = function ()
  {
     var n = this.length;
     do {
        var swapped = false;
        for (var i = 1; i < n; i++ ) {
           if (this[i - 1] > this[i]) {
              var tmp = this[i-1];
              this[i-1] = this[i];
              this[i] = tmp;
              swapped = true;
           }
        }
     } while (swapped);
  }

  /**
   * Quick sort
   */
  Array.prototype.quickSort = function ()
  {
      if (this.length <= 1)
          return this;

      var pivot = this[Math.round(this.length / 2)];

      return this.filter(function (x) { return x <  pivot }).quickSort().concat(
             this.filter(function (x) { return x == pivot })).concat(
             this.filter(function (x) { return x >  pivot }).quickSort());
  }

- Dmitry Balabka

---

我认为调用 filter，quickSort和concat使quickSort变得非常缓慢。 - JiminP

Answer 1

这是因为当你对已排序的数组进行排序时，冒泡排序算法速度更快。

因为在第一次测试中，你对同一个数组进行排序后它就已经排好序了，接下来你再次对已排序的数组进行排序。

如果要测试对未排序的数组进行排序的实际性能，则需要为每个排序迭代创建一个新数组。

- Guffa