我们之前文章里面讲到的排序基本上都是比较排序，不管是冒泡排序、快速排序还是插入排序等等，都是基于元素之间的比较来进行一个整体的排序，那有没有一种排序是可以不用进行元素间的对比就可以完成整个序列的升序或者降序呢？当然有，计数排序就不用元素之间的相互比较，而是通过元素的下标来确定每个元素的位置从而进行排序，在某些特殊的时候，它的排序速度甚至比快速排序还要快。

举个例子，现在有一组待排序的数字（如图1-1所示），怎么通过计数排序进行升序排序呢？

图1-1

首先，通过观察我们会发现数组里的元素的取值范围为0——9，于是我们可以创建一个长度为9（元素最大值）的数组，元素的初始值都为0，如图1-2所示：

图1-2

遍历原始数组，让每一个整数按照值对号入座，对应数组下标的元素加1，第一个元素为8，就在数组下标为8的元素加1（如图1-3所示）

图1-3

按照此方法，依次遍历后面的元素，最后得到的结果如图1-4所示：

图1-4

最后，按照下标的先后顺序依次将下标输出，该下标的元素是几，就将下标输出几次，最后就会得到一个顺序为升序的数组，如图1-5所示：

图1-5

其实从上面的步骤中可以看出来计数排序是比较简单的排序，效率也是比较高的，但是他还是有一定的局限性，只适合一些特殊的序列，元素数值跨度不能太大，范围最好在0~100之间，一组数值比较相邻的待排序序列更加适合用计数排序。

以上呢，就是对最基础版的计数排序的详细解释，接下来我们来看一下怎么把这些步骤通过C语言进行实现。

代码实现：

#include <stdio.h>

void sort(int *A, int *B, int len, int k)

{

            int C[k+1], i, value, pos;  // 定义一个数组C，为辅助数组

            for(i=0; i<=k; i++)  // 为C数组进行初始化，元素值都为0

            {

                C[i] = 0;

            }

            for(i=0; i< len; i++)  // 统计A数组中i元素的个数

            {

                C[A[i]] ++; 

            }

            for(i=1; i<=k; i++)  // 统计A元素中小于等于I元素的个数 

            {

                C[i] = C[i] + C[i-1];

            }

            for(i=len-1; i>=0; i--)  // 进行排序，将排完序的值放到B数组中

            {

                value = A[i];

                pos = C[value];

                B[pos-1] = value;

 C[value]--;                                                                                                       

            }

}

int main()

{

 //定义一个原始数组A，长度为9  定义一个数组B，用来存储排完序的元素

            int A[9] = {8,4,5,7,3,6,1,0,9}, B[9], i;

            sort(A, B, 9, 9);    // 调用sort函数，传四个参数：数组A、数组B 、数组长度、最大元素值

            for (i=0; i<= 8; i++)

            {

                printf("%d ", B[i]);

            }

            printf("\n");

            return 0;

}