計數排序

對每一個輸入元素x，確定小於x的元素個數。利用這一信息，可以直接把x放到它在輸出數組中的位置上。假設輸入一個數組A[1..n]，我們需要兩個數組：B[1..n]存放排序的輸出，C[0...k]提供臨時存儲空間。

Counting-sort(A,B,k)let C[0..k] be a new arrayfor i = 0 to k C[i] = 0for j = 1 to A.length C[A[j]] = C[A[j]] + 1for i = 1 to k C[i] = C[i] + C[i-1]for j = A.length downto 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1

#pythondef count_sort(A,B,k): C = [] for i in range(0,k): C.append(0) for j in range(0,len(A)): C[A[j]] = C[A[j]] + 1 for i in range(1,k): C[i] = C[i] + C[i-1] for j in range(len(A)-1,-1,-1): B[C[A[j]]-1] = A[j] C[A[j]] = C[A[j]] - 1

推薦閱讀：