計算排序基本資訊
Counting sort 是一個整數排序演算法，用於根據物件的鍵進行排序的物件集合。
腳步
- 構造一個工作陣列 ç 具有大小等於輸入陣列範圍A。
- 通過 A 迭代，根據 x 出現在 A 中的次數分配 C [x] 。 **
- 將 C 轉換為一個陣列，其中 C [x]通過遍歷陣列指向值的數量≤x，為每個 C [x]指定其先前值和 C 之前的所有值之和。
- 向後遍歷A，將每個值到一個新排序後的陣列B記錄在索引處 Ç 。對於給定的 A [x]，通過將 B [ C [ A [x]]]分配給 A [x]來完成，並且在原始未排序的陣列中存在重複值的情況下遞減 C [ A [x]]。
計數排序的示例
http://i.stack.imgur.com/ccdTK.jpg
輔助空間： O(n+k)
時間複雜度： 最壞情況：O(n+k)，最佳情況：O(n)，平均情況 O(n+k)