1. 简介
计数排序（counting sort）于1954年由哈罗德·H·西华德（Harold H. Seward）提出。计数排序是一种基于数组键值的正整数排序算法，通过对等于不同键值的数据进行计数，从而获得待排序序列的位置关系。由此，这种算法不是基于比较排序，并且比较排序的性能下限 O ( n log n ) O{\left(n\log n \right)} O(nlogn)不适用于计数排序。计数排序的时间复杂度和空间复杂度都为 O ( n + k ) O{\left(n+k\right)} O(n+k)
计数排序与其他算法不同，需要一些前提条件：
- 待排序序列中每个元素的值都 ≥ 0 \ge 0 ≥0。
- 待排序序列数组的键值都 ≥ 0 \ge 0 ≥0。
- 知道待排序序列中的最大值
k。（不知道的情况下，则遍历待排序序列求得最大值）
2. 步骤
- 根据最大值
k申请一个长度为k + 1的数组以存储元素计数，并且全部初始化为0。可以把这个序列叫做计数数组。 - 申请一个和待排序序列等长的数组用以存储排序后的数据。
- 遍历待排序序列，如果元素等于计数数组的键值，则键值的值
+1。 - 根据计数序列的值计算演算出所有位置（索引数列）。
- 再次遍历待排序序列将，所有数放入计数序列的指定位置。
举例：
待排序序列为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | 6 | 0 | 6 | 3 | 5 | 2 | 5 | 2 |
得最大值为 k = 6 申请一个长度为 k + 1 的计数数组
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
计数数组的键值等于待排序元素的值，遍历待排序序列得计数数组为：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 0 | 2 | 2 |
接着就是根据计数数组得元素的排序位置（不断累加计数）：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 计数 | 1 | 1 | 2 | 2 | 0 | 2 | 2 |
| 索引 | 0 + 1 = 1 0+{\color{red}1}={\color{red}1} 0+1=1 | 1 + 1 = 2 1+{\color{red}1}={\color{green}2} 1+1=2 | 2 + 2 = 4 2+{\color{green}2}={\color{blue}4} 2+ |
