计数排序（线性时间排序）--[算法导]

之前的排序都是通过比较得到的，即比较排序：在排序的最终结果中，各元素的次序依赖与它们之间的比较。而时间复杂度最好的也是O(nlgn)，接下来说一个未经比较的排序，而复杂度则是线性的。

计数排序:假设n个输入元素的每一个都是在0-k区间内的一个整数，其中k为某个整数。当k = O(n)时，排序的运行时间为O(n)。

计数排序的基本思想是：对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了。例如，如果有17个元素小于x，则将x放在第18个位置即可。但是当存在几个元素相同时，会稍许不同，否则中间会漏掉元素。

在计数排序算法中，假设输入是一个数组A[1..n]，A.length = n。另外数组B[1...n]存放排序的输出，C[0...k]提供临时的存储空间：

第1-2行，C数组赋值为0；

第3-4行，记录各个元素的个数，下图中a图；

第6-7行，对数组C操作，C[i] = C[i] + C[i- 1];见下图中b图

第9-11行，排序...下图中c，d，e图是执行9-11代码一次、二次、三次的结果，f是结果；

代码：

#include 
  
   
#include 
   
     using namespace std; /*int Max(int A[], int length) { int max = A[0]; for(int i = 1; i < length; i++) { if(max < A[i]) max = A[i]; } return max; }*/ int CountSort(int A[], int* B, int k, int length) { int *C = new int[k]; memset(C, 0, sizeof(int) * (k)); for (int j = 0; j < length; j++) //辅助C { C[A[j]] += 1; } for (int i = 1; i < k; i++) // { C[i]= C[i]+C[i-1]; } for (int j = length - 1; j >= 0; j--) { B[C[A[j]] - 1] = A[j]; C[A[j]] = C[A[j]] - 1; //若是出现同样的数往前放 } delete[] C; return 0; } int main() { int A[] = {2, 5, 3, 0, 2, 3, 0, 3}; //int A[] = {2, 9, 7, 1, 3, 5, 11, 4, 12, 35}; int length = sizeof(A) / sizeof(int); // int* B = new int[length]; int k = 10001; //保证排序数据在0-k中 //k = Max(A, length) + 1; //k = max + 1;后面方便操作 CountSort(A, B, k, length); //计数排序 for(int i = 0; i < length; i++) cout<