爲什麼選擇排序如此之快的JavaScript？

我正在學習技術面試，並編寫不同種類的快速JavaScript實現。大多數基本排序的隨機數組基準結果是有意義的，但是選擇排序的速度非常快。我不知道爲什麼。爲什麼選擇排序如此之快的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種元素的結果：
冒泡=> 148ms
插入排序=> 94ms
選擇排序= > 91ms
MergeSort => 45ms

所有類型都使用相同的交換方法。那麼爲什麼選擇排序更快？我唯一的猜測是，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; 
};

來源

2014-05-03 Hao Luo

你可以看看你的實現是否正確：檢查結果數組是否被排序。 – 11684

那麼你應該可以通過遍歷一次數組來輕鬆驗證你的結果，檢查下一個數字是否大於前一個數字（反之亦然）。 – Daniel

是的結果是正確的。我只是不確定我的實現是否真的是選擇類型......如果是這樣，爲什麼它如此之快 –

首先我想指出兩個缺陷：

您選擇排序的代碼有問題。內循環需要爲
```
for (var j = target + 1; j < this.length; j++) { 
```
否則最後一個元素從不被選中。
您的jsperf測試按照您的說法每次排序「相同的隨機生成的數組」。這意味着每個測試循環中的連續運行將嘗試對已經排序的數組進行排序，這將有利於具有線性最佳情況性能的諸如bubblesort之類的算法。

幸運的是，您的測試數組非常大，以至於jsperf一次只運行一次它的測試循環迭代，調用在每次運行前初始化數組的初始化設置代碼。儘管如此，這會讓你困擾更小的陣列。你需要在「定時代碼」本身內部洗牌數組。

爲什麼選擇排序更快嗎？我唯一的猜測是Javascript在數組遍歷中真的很快，但是在值變化上很慢。

是的。寫入總是比讀取更慢，並且對緩存值也有負面影響。

選擇排序使用至少價值突變

是的，這是相當顯著。選擇和冒泡排序都有一個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

Ooops。

來源

2014-05-04 13:03:31 Bergi

感謝您的真棒回答！我昨晚看到了代碼中的錯誤，並修復了它:) –

爲什麼選擇排序如此之快的JavaScript？

回答

相關問題