測試快速排序

-2

的速度，我讀算法第四版普林斯頓的書，並觀看了在線課程視頻。我發現了兩件有趣的事情。測試快速排序

它在視頻中說，如果我們在快速排序使用截止這樣的，我們將通過10〜20％，加快程序：

如果（HI - LO < CUTOFF）插入。排序（一）;

它建議，當我們使用遞歸公式對數組的分成子陣列，和排序子陣列遞歸，我們可以使用插入排序算法當子陣列的尺寸比CUTOFF instead.However小，當我測試它與CUTOFF大小3,7和10.它不是這種情況。這在我的測試數據集中慢了大約10倍。數據集是5000個隨機數的數組。所以我想我們最好不要對小尺寸數組使用插入排序。

當我嘗試測量代碼的運行時間並將其與本課程的標準代碼（即algs4.jar庫）進行比較時。我發現我的時間更長，即使我將我的代碼更改爲標準代碼。最後，我意識到，即使我們QUICKSORT同一陣列的兩倍（複製數組作爲A1，A2），第二排序的運行時間將永遠是一半左右的第二排序的運行時間。即（僞碼）： stopWatch sw1 = new stopWatch（）; quicksort（a1）; print sw1.elaspedTime（）;
```
stopWatch sw2 = new stopWatch(); 
quicksort(a2); 
print sw2.elaspedTime(); 
```

然後第二個成本大約一半時間，即使它們是相同的算法和排序在同一陣列。我不知道爲什麼會發生這種情況。這是一個非常有趣的現象。

來源

2014-10-03 ohmygoddess

做你自己實現快速排序，或者您使用的構建在一個 – Steve 2014-10-03 22:20:56

我自己實施和比較書中的代碼。最後，我改變了我的代碼，就像這本書一樣。結果與上面描述的相同 – ohmygoddess 2014-10-03 22:24:22

我幾乎100％確定如果您更改測試器算法的執行順序，您將得到其他結果。 JVM需要時間來蠕變。 – 2014-10-03 22:28:56

現在。理論上它可能會更快，但取決於您使用的語言，編譯器，系統和CPU，它可能會有所不同。我可以用你的第二點作爲例子。 CPU有一些叫緩存的東西，它可以容納頻繁使用的數據來提高速度。它非常小，但速度超快，比RAM更快。因此，基本上第一次運行程序時，該數組最初在內存中，並且在緩存未命中時進入緩存。當你第二次運行相同的代碼時，一切都已經在緩存中了，不需要在RAM中查找它，也不需要緩存丟失，所以它比第一次運行更快。如果你想準確的結果，那麼你可能需要清除RAM清除緩存，關閉所有正在運行的程序和ECT

來源

2014-10-03 22:26:08 Steve

Got you！有道理。謝謝！ – ohmygoddess 2014-10-03 22:28:23

測試快速排序

回答

相關問題