計數排序

計數排序

計數排序假設n個輸入元素中的每一個都是0到k區間内的一個整數，其中k為某個整數。當

k=O(n)時，排序的運作時間為@(n)

計數排序的基本思想是： 對每一個輸入元素x，确定小于x的元素個數。利用這個資訊，就可以直接把x

放到它在輸出數組中的位置上了。 例如，如果有17個元素小于x，則x就應該在第18個輸出位置上。當有

幾個元素相同時，這一方案要略作修改。因為不能把它們放在同一個輸出位置上。

在計數排序算法的代碼中，假設輸入是一個數組A[1...n], A.length=n. 我們還需要兩個數組，B[1..n]

存放排序的輸出，C[0...k]提供臨時存儲空間。

COUTING-SORT(A,B,k)

let C[0...k] be a new array

for i=0 to k

    C[i] = 0

for j=1 to A.length

    C[A[j]] = C[A[j]] +１

//C[i] now contains the number of elements equal to i.

for i=1 to k

    C[i] = C[i] + C[i-1]

//C[i] now contains the number of elements less than or equal to i

for j=A.length downto l

    B[C[A[j]]] = A[j]

    C[A[j]] = C[A[j]] - 1

本文轉自莫水千流部落格園部落格，原文連結：http://www.cnblogs.com/zhoug2020/p/6189084.html，如需轉載請自行聯系原作者