Array.prototype.sort暫時重複內容？

我最近想通過Array.prototype.sort如何使用自定義方法來比較任何給定時間的兩個值，並決定它們是應該交換還是單獨放置。我決定在每次比較過程中記錄數組，以便可以看到前面比較的結果。當我登錄數組時，我注意到某些時刻數組狀態相當奇怪。Array.prototype.sort暫時重複內容？

假設如下：

var num = [ 2, 1, 8, 5, 3 ]; 

num.sort(comparator); 

function comparator (a, b) { 
    console.log(num); // Current state of num 
    return a - b; // Order values numerically 
}

這是輸出：

[ 2, 1, 8, 5, 3 ] // Comparing 2 and 1 
[ 1, 2, 8, 5, 3 ] // Comparing 2 and 8 
[ 1, 2, 8, 5, 3 ] // Comparing 8 and 5 
[ 1, 2, 8, 8, 3 ] // Comparing 2 and 5 
[ 1, 2, 5, 8, 3 ] // Comparing 8 and 3 
[ 1, 2, 5, 8, 8 ] // Comparing 5 and 3 
[ 1, 2, 5, 5, 8 ] // Comparing 2 and 3

數組是正確（[ 1, 2, 3, 5, 8 ]）進行分類，但我仍然留在一些對通行證的抓我的頭收集本身。

8號在迭代4上出現兩次，暫時替換5是怎麼回事？再次，8次出現兩次，兩次迭代後暫時取代3次。最後，5出現兩次，在上次迭代中暫時替換3次。

請注意，上面的代碼是在Chrome中運行的。

來源

2013-10-08 Sampson

現在嘗試一個更長的數組。不同的行爲？檢查10-ish邊界是否有差異;看起來像插入排序-y。 10+可能quicksort-y？ IIRC它根據尺寸而變化，但是它是在一段時間以前我想過的。 –

@DaveNewton有趣的想法，但有13個項目似乎仍然暫時複製比較索引內容。雖然沒有考慮到實施可能會改變取決於集合的大小。 – Sampson

它從來沒有被檢查的項目'console.log（a，b，num）;' –

有趣，但不是太令人驚訝。

它似乎在這種情況下使用簡單的插入排序算法。

線沿線的東西：

獲取項目[1]
Shift鍵在它下面的每個項目最多一個，直到你發現是低的項目，那麼這個項目上面放
獲取項目[ 2]
移每個項目下面的它，直到找到那下一個項目，然後把它放在這個項目上面
獲取項目[3]
（續）

當描述氣泡排序算法時，通常想象每個元素都沿着數組交換，直到找到它的位置。但將項目存儲到臨時變量中比將其交換更有效。

來源

2013-10-08 21:50:47

我已經考慮過這個問題，但是找不到一個爲什麼一些迭代會導致重複值的原因，而另一些則不會。如果每次迭代都會導致重複值，然後進行更正，這對我來說似乎更加明顯。 – Sampson

這個特定版本的氣泡排序通常被稱爲「inserion排序」 –

@JonathanSampson只有移動到左邊的元素會暫時在插入排序中刪除 –

Array.prototype.sort暫時重複內容？

回答

相關問題