排序雙向列表

如果我有一個包含0和1的二進制值的列表，如下面的000111010110 ，我想將它排序到下面的000000111111如果你也知道如何做到這一點，最有效的方法是什麼？列表大小？現在我正在考慮有一個計數器，在我從開始到結束遍歷列表時，我只計算0的數量。然後，如果我通過numberOfZeros除listSize我得到numberOfOnes。然後我想着，而不是重新排序從零開始的列表，我只是創建一個新的列表。你會同意這是最有效的方法嗎？排序雙向列表

來源

2012-10-26 Q Liu

如果您正在使用電腦的話位工作，多數民衆贊成，然後查看http://graphics.stanford.edu/~seander/bithacks.html的計數位設置部分。 –

您的算法實現了經典bucket sort算法（其實現爲counting sort）的最原始版本。當數字範圍已知時，它是對數字進行排序的最快方法，並且（相對）較小。由於零和零是你所擁有的，所以你不需要在存儲分類中存在的一系列計數器：一個計數器就足夠了。

來源

2012-10-26 16:11:35 dasblinkenlight

如果您有數字值，則可以使用匯編指令bitscan（x86彙編中的BSF）來計數位數。要創建「排序」值，您可以設置n + 1位，然後減1。這會將所有位設置在n + 1位的右側。

來源

2012-10-26 17:38:45

BSF找到第一個比特集的索引。它不會計算所設置的位數。 –

第二個建議是好的。 –

我認爲你的意思是POPCNT。 – hammar

桶排序似乎是一種排序算法。

我不認爲有這樣的操作需要。我們知道沒有排序算法比N * logN更快。所以默認情況下它是錯誤的。

而所有你需要做的就是你一開始就說過的話。只要遍歷這個列表並計算零或者那個會給你O（n）複雜度的東西。然後，創建一個新的數組在開始之後計數爲零，然後是1。然後總共有N + N的複雜度，這使得O（n）的複雜性成爲可能。

而且只是因爲你只有兩個values.So既不快速排序或任何其他類型的可以做到這一點faster.There沒有更快的排序比NLOG（N）

來源

2012-10-27 03:10:42

排序雙向列表

回答

相關問題