1.計數(shù)排序特點

1.一般輸入的關(guān)鍵字都在0到k區(qū)間內(nèi)的一個整數(shù)，其中k為某個整數(shù)；
2.當(dāng)輸入的元素個數(shù)為n時，排序的時間復(fù)雜度為O(n)；
3.計數(shù)排序需要額外的空間，k越大需要的額外空間越大，因為需要k長度的數(shù)組；

2.計數(shù)排序介紹

計數(shù)排序的基本思路：對每一個輸入元素x，確定小于x的元素個數(shù)（假設(shè)為a），那么x可放到輸出數(shù)組的a位置上。例如，如果有10個元素小于x，則x就應(yīng)該放在第11個輸出的位置上。

3.計數(shù)排序的偽代碼

假設(shè)輸入是一個數(shù)組A [0..n-1]，A.length = n。需要另外兩個數(shù)組：B[0..n-1]存放排序后輸出，C[0..k]提供計數(shù)使用。

COUNTING-SORT(A,B,k)
let C[0,k] to be a new array
// 重置C[0..k]個元素為0
for i = 0 to k  
    C[i] = 0;
// A[0..n-1]數(shù)組中A[j]有幾個計數(shù)在C[A[j]]上
for j = 0 to A.length -1
    C[A[j]] = C[A[j]] + 1
// 計算A[0..n-1]中比A[j]小的個數(shù)，即C[0..k]中比A[j]下標(biāo)小的計數(shù)之和（這里需要理解一下，
//比如A[10] = 30，那么C[0..29]是對應(yīng)A[0..n-1]數(shù)組中0到29的個數(shù)，0到29可能有些數(shù)沒有，對應(yīng)的個數(shù)為0）
for i = 1 to k
    C[i] = C[i] + C[i - 1]      // C[i]即為i = A[x]的小于等于i的個數(shù)
// 把A[0..n-1]排序輸出到B[0..n-1]
for j = A.length-1 downto 0
    count = C[A[j]]
    B[count -1] = A[j]
    C[A[j]] = C[A[j]] - 1       // 把A[j]的個數(shù)減1

圖解步驟如下：

算法-計數(shù)排序1.png