计数排序是一种能够达到运行时间能够线性时间θ(n)的排序算法。在排序算法里算是最快的算法之一，当然，他有很强烈的前提。下面开始介绍一下计数排序（Counting Sort）。
算法思想
计数排序假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数。这样可以用一个数组C[0..k]来记录待排序数组里元素的数量。当k=O(n)时，计数排序的运行时间为θ(n).
注：关于C[0..k]，用键值对描述的话，待排序元素是键，相同元素的个数是值。例：待排序数组<2，3 , 6，4 , 1 , 1 , 3 , 5 , 7> 一共9个元素，切每一个都处于0到7之间，故设数组C[0..7] ，有C[2] = 1 ， C[3] = 2，因为数组里只有1个2，有两个3
计数排序基本思想：对每一个输入元素x，确定出小于x的元素个数，有了这个信息，就能将x放在属于它的正确的位置上（当有元素相同时，方案就要略加修改）。
算法的伪代码实现
计数排序会有三个数组：
A[1..n] 待排序数组
B[1..n] 排序结果存放数组
C[0..k] 临时存储区
计数排序过程：
- 将C[0..k]中的全部元素置为0
- 遍历数组A[1..n]，将里面各个元素的个数记录到数组C
- 使用数组C记录小于等于各个元素的元素的个数
- 小于等于每个元素的元素个数就是这个元素在新数组里的位置
- 排序完成
书中的伪代码实现：
算法的C++实现
#include <iostream>
using namespace std;
const int COUNT = 15;
// 计数排序
void counting_sort(int* a, int* b, int k);
int main() {
int a[COUNT] = {
2, 3, 1, 3, 4,
6, 9, 6, 5, 7,
1, 0, 10, 2, 4
};
// 最大值为10,所以 k = 10
int k = 10;
int b[COUNT];
// 排序，将排序结果放到数组 b 中
counting_sort(a, b, k);
// 输出排好序的值
for (int i = 0; i < COUNT; i++) {
cout << b[i] << " ";
}
cout << endl;
getchar();
return 0;
}
// 计数排序
void counting_sort(int* a, int* b, int k) {
// 声明数组 C，并将 C 中所有值置为 0
int *c = new int[k+1];
for (int i = 0; i < k+1; i++) {
c[i] = 0;
}
// c[a[i]] 中是与a[i]这一个元素相同值的元素个数
for (int i = 0; i < COUNT; i++) {
c[a[i]] = c[a[i]] + 1;
}
// c[i]中是小于等于 i 的元素的个数
for (int i = 1; i < k+1; i++) {
c[i] = c[i] + c[i - 1];
}
// c[i] 就是 i这个元素在排序数组里的位置
for (int i = COUNT-1; i >= 0; i--) {
b[c[a[i]]-1] = a[i]; // 这里是c[a[i]] - 1，因为C++数组从0开始，伪代码从1开始
c[a[i]] --; // 考虑两个元素相等,下一个与当前元素相等的元素放在前面
// 又因为这是从后往前遍历，所以相等数的相对位置没变，故这是一个稳定的排序算法
}
free(c);
}
- 里面虽然有四个循环，但每个循环的时间复杂度都是O(n)，故总的时间复杂度为O(n)
- 这种排序算法没有比较两个元素的大小，所以突破了比较排序的下限O(nlgn)
- 另外，在代码的注释也有写，在排序过程中相等数的相对位置没变，所以这是一个稳定的排序算法