为什么Javascript的Bubble排序比其他排序算法快得多？

Question

我已经做了一些关于使用Javascript排序算法性能比较的research，并且发现了意想不到的结果。泡泡排序提供比其他更好的性能，例如Shell排序，快速排序和本地Javascript功能。为什么会发生？也许我在我的性能测试方法中错了？

您可以查看我的研究结果here。

这里有一些算法实现的例子：

/** 
    * 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()); 
    } 

Answer 1

这是因为冒泡排序更快，当你选的是已经排序的数组。

由于您一遍又一遍地对相同的数组进行排序，它将在第一次测试的第一次迭代中排序，然后对已经排序的数组进行排序。

要测试排序尚未排序的数组的实际性能，必须为每个排序迭代创建一个新数组。