性能計數排序

Question

AFAIK counting sort的是使用下面的算法：

// A: input array 
// B: output array 
// C: counting array 
sort(A,B,n,k) 
1. for(i:k) C[i]=0; 
2. for(i:n) ++C[A[i]]; 
3. for(i:k) C[i]+=C[i-1]; 
4. for(i:n-1..0) { B[C[A[i]]-1]=A[i]; --C[A[i]]; } 

什麼我刪除步驟3和4，並做以下？

3. t=0; for(i:k) while(C[A[i]]) { --A[i]; B[t++]=i; } 

的完整代碼here，貌似不錯，但我不知道哪一個具有更好的性能。

問題：

1. 我猜這兩個版本的複雜性將是相同的，是TURE？
2. 在步驟3和步驟4中，第一個版本需要迭代n + k次，第二個版本只需要迭代n次。第二個有更好的表現嗎？

Answer 1

您的代碼似乎是正確的，它會在排序數字的情況下工作。但是，假設您有一組根據其鍵進行排序的結構。你的方法在這種情況下將不起作用，因爲它只是計算一個數字的頻率，而當它保持正值時，則將它分配給輸出數組中的增加索引。然而，經典的方法將適用於結構和對象等數組，因爲它計算每個元素應該到達的位置，然後將數據從初始數組複製到輸出數組。

爲了回答您的問題：

1>是，您的代碼的運行時的複雜性將是相同的，因爲對尺寸n和範圍0...k的陣列，您的內部和外部循環中運行成正比f(0)+f(1)+...+f(k)，其中f表示數字的頻率。因此運行時間是O（n）。

2>就漸近複雜度而言，兩種方法都具有相同的性能。由於額外的循環，常數可能會更高。但是，這也使經典方法穩定分類，並具有我前面指出的好處。