计数排序是需要假设输入数据的排序之一，它假设输入元素是0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，计数排序的时间复杂度为θ（n）。
因为不是通过比较来排序，所以它的时间复杂度可以达到θ（nlgn）以下。
计数排序是稳定的排序之一。
代码如下：（仅供参考）
//计数排序期望输入数据都是小区间内的整数 void CountingSort(int * const begin, int * const end) { vector<int> temp(10000); //假设输入值小于10000 vector<int> out(end - begin); for (int i = 0; i < end - begin; ++i) ++temp[*(begin + i)]; for (int i = 1; i < 10000; ++i) temp[i] += temp[i-1]; for (int i = end - begin - 1; i >= 0; --i) { out[temp[*(begin + i)] - 1] = *(begin + i); --temp[*(begin + i)]; } for (int i = 0; i < end - begin; ++i) *(begin + i) = out[i]; }
原文：https://www.cnblogs.com/yxsrt/p/12193682.html