快速排序算法：我不斷得到一個不同的答案

我正在努力研究本週二即將到來的測試的各種排序和搜索算法。一切都很順利，直到我找到了快速排序算法。我沒有書或任何其他資源，所以我上網並開始閱讀SparkNote。我以爲我理解了文本，甚至閱讀了我在網上找到的PowerPoint的快速排序算法部分。快速排序算法：我不斷得到一個不同的答案

但是，SparkNote在算法的分步過程的頁面上提供了一個示例，但它沒有顯示初始排列列表的步驟。給出的列表是[5 9 3 8 6 4 2 1 7 0]。根據SparkNotes，排列的列表中的值小於左側的數據點（其值爲5），而數值大於右側的數據點的值爲[0 3 4 2 1 5 8 6 7 9]。但是，當我嘗試自己完成這些步驟時，我總是收到[ 4 0 3 1 2 5 6 8 7 9 ]。

我把程序是：

5 9 3 8 6 4 2 1 7 0 // The initial list. Pivot = 5 
5 0 3 8 6 4 2 1 7 9 // Switched 0 and 9. 
5 0 3 1 6 4 2 1 7 9 // Switched 8 and 1 
5 0 3 1 2 4 6 8 7 9 // Switched 6 and 2 
4 0 3 1 2 5 6 8 7 9 // Switched 4 and 5 because the lines that point to the 
        // greater and smaller numbers crossed.

哪裏是我的錯？另外，我看到小於5的數字在左邊，大於5的數字在右邊，所以，我的錯誤是否真的影響了排序？

來源

2012-08-11 kullalok

有很多不同的方法來分區快速排序數組。只需Google「quicksort分區」即可找到多個示例。 – Blastfurnace 2012-08-11 20:27:50

SparkNotes中描述的算法最初將主元素放置在數組中最右邊的位置。您使用的算法放置/保持關鍵點位於最左邊的。難怪分區之後的安排是不同的。

這意味着，它們開始與

5 9 3 8 6 4 2 1 7 0

選擇5作爲樞軸並把它放在最右邊的位置（交換5和0）

0 9 3 8 6 4 2 1 7 5

只有經過它們進行分割爲其餘元素。

您在最左邊的位置（顯然你只是忘記從的SparkNotes執行步驟2）保持你的5。最後，兩種變體都可以工作，即沒有「錯誤」。在你的情況下，這個安排對陣列正確分區是完全有效的。

來源

2012-08-11 20:22:39 AnT

您沒有按照精確算法上的SparkNotes站點呈現。他們的第二步要求您將樞軸與最後一個元素交換。

在任何情況下，對於算法而言，如何精確執行分區都是無關緊要的，只要您將該序列分割爲使得所有元素在主元之前都小於（或等於）主元和其後的元素更大（或相等）。當你遞歸地對結果分區進行排序時，你最終會得到一個排序序列。

它的效率，而不是正確的事，你如何處理等元素，以及如何選擇樞軸，以及在什麼序列長度你最終切換到另一種算法。

來源

2012-08-11 20:27:36

Here你可以看到視覺實施Quick-sort算法。

也許你還會發現有用：

如果你恨匈牙利民間舞蹈不要去鏈接。 :)

來源

2012-08-11 20:37:51

快速排序算法：我不斷得到一個不同的答案

回答

相關問題