计数排序假设n个输入元素中的每一个都是介于0到k之间的整数。其基本思想就是对每个输入元素x，确定小于x的元素个数。有了这一信息，就可以把x直接放到它在最终输出数组中的位置上。

1 #include
     
       2  void countsort(int *A,int *B,int n,int k) 3  { 4      //输入检查 5  6  7      int *C = new int[k];//记录小于输入x的个数 8      for (int i = 0; i < k;++i) 9      {10          C[i] = 0;11      }12      for (int i = 0; i < n;++i)13      {14          C[A[i]] = C[A[i]] + 1;15      }16 17      for (int i = 1; i < k;++i)18      {19          C[i] = C[i - 1] + C[i];20      }21 22      for (int i = n - 1; i >= 0;--i)23      {24          B[C[A[i]]-1] = A[i];25          --C[A[i]];26      }27      delete[] C;28  }29 30  int main()31  {32      int a[] = { 8, 4, 5, 6, 7 };33      int *B = new int[5];34      memset(B, 0, sizeof(int) * 5);35      countsort(a, B, 5, 9);36      for (int i = 0; i < 5;++i)37      {38          std::cout << B[i] << ' ';39      }40 41      delete B;42  }