计数排序基本思想

对每个输入元素x，确定小于x的元素个数，利用这一信息，可以直接把他放在输出数组中的位置上了

元素数量n,每个元素值介于0到k

总的时间代价是O(k+n)

实际工作中时间复杂度O(n)

代码

1  .CountSort(int *A, int *B, int k) { //C是一个临时数组
2  .    for(int i = 0; i <= k; i++) {
3  .        C[i] = 0;
4  .    }
5  .    for(int i = 1; i <= n; i++) {
6  .        C[A[i]] = C[A[i]]+1;
7  .    }
8  .    for(int i = 1; i <= k; i++) {
9  .        C[i] = C[i] + C[i-1]; 
10 .    }
11 .    for(int i = n; i >= 1; i--) {
12 .        B[C[A[i]]] = A[i];
13 .        C[A[i]] = C[A[i]] - 1; 
14 .    }
15 .}

例子

图演示的是计算过程，2，3行将C数组赋值为0。

4，5行循环遍历数，如果输入的数值为i，则将C[i]加1,得到(a)

7，8行计算对于每个i=1，2…k,有几个输入元素是小于等于i的，得到(b)

最后把答案写到B数组，经过经过(d)(e)，得到(f)

文章目录

计数排序基本思想

代码

例子