计数排序是一种能够达到运行时间能够线性时间θ(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] 临时存储区
计数排序过程： 1. 将C[0..k]中的全部元素置为0 2. 遍历数组A[1..n]，将里面各个元素的个数记录到数组C 3. 使用数组C记录小于等于各个元素的元素的个数 4. 小于等于每个元素的元素个数就是这个元素在新数组里的位置 5. 排序完成
书中的伪代码实现：
算法的C++实现;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 = 10int 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) {[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);}
世界会向那些有目标和远见的人让路(冯两努–香港着名推销商
