快速排序二進制數組

我想知道在最糟糕的情況下，Quicksort需要對大小爲n的二進制數組進行排序有多少次比較。
我無法找出這個問題最糟糕的情況。 [0 1 0 1 0 1..]？
乾杯，
EO快速排序二進制數組

2012-11-17 eouti

最壞的情況下爲O（N2）無關的內容，但平均起來將是爲O（n log n）的 –

如果您知道數組只包含0和1，則不要使用快速排序。一個分區傳球就足夠了。 –

我知道這不是使用快速排序的最佳方式，但我需要知道它在這個問題上的最差情況 – eouti

不完全是快速排序，但如果你想進行排序二進制數組，你可以做到這一點在爲O（n）。只要計算你有多少個1和0，然後按你想要的順序寫。

例如，對於下面的數組：

[0 1 0 1 0 1 1]

你可以指望，在O（n）的，你有三個0和四個1的。然後你只需要用三個0重寫你的數組，然後再用四個1重寫。

2012-11-17 17:19:29

但在這種情況下，您通過數組迭代2次一個用於計數，另一個用於寫入 –

正確，但算法爲O（n）。 –

第二回合不執行關鍵比較。 –

排序由少量唯一鍵組成的數組在實踐中很常見。當唯一鍵的數量是O（1）時，人們會喜歡一種適應O（n）時間的算法。在你的情況下，只有兩個唯一的鍵。

快速排序是最壞的情況下，你的情況我已經測試了快速排序算法這個數組[ 0 1 1 0 1 0 1 0 0 0 1 0 1 ]在O（nlogn）的平均水平，但爲O（n^2），數組的lenght是13元素，和算法採用170迭代對此數組進行排序，即n^2。

併爲O（n）的算法，這個僞代碼：

let n0 <- 0; 
for i=0 to lenght(A) 
    if A[i] == 0 
     A[n0] = 0; 
     ++n0 

for i=n0 to lenght(A) 
    A[i] = 1

2012-11-17 21:02:13

回答