概述

计数排序与其它排序并不一样，其它排序是基于比较进行排序，而计数排序是通过计算一个集合中元素出现的次数来确定集合的排序。

计数排序只适用于整型或者那些可以用整型来表示的数据集合，因为计数排序需要利用数组的索引来记录元素出现的次数。例如，如果整数n出现m次，那么m将存储到数组索引为n的位置上。这要求我们需要知道集合中最大的整数值，便于为数组分配足够的空间。

计数排序属于稳定排序，顺便说一下排序算法稳定性的定义，两个相同的元素的相对位置不发生变化，则该算法具有稳定性。

算法分解

1. 获取最大值，申请临时的连续空间
2. 获取每个元素出现的次数，并使用数组记录
3. 计算每个元素前面元素的个数
4. 根据元素前面的所有元素个数，将元素放在临时空间的对应位置

例子

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

/*****************
计数排序主要用于整型序列的排序
申请额外的空间，保存每个元素出现的次数
由小于该元素的元素出现次数，决定元素所在的位置
*****************/

void csort(int *src,int *dst,int size,int k)
{
    int i;
    int *count = malloc(size*sizeof(int));
    for(i=0;i<k;i++)
    {
        count[i] = 0;
    }
    for(i=0;i<size;i++)
    {
        /*计数每个元素出现的次数*/
        count[src[i]]++;
    }
    for(i=1;i<k;i++)
    {
        /*计算每个元素该在的位置*/
        count[i] += count[i-1];
    }
    for(i=0;i<size;i++)
    {
        /*将元素存放在该在的位置*/
        dst[--count[src[i]]]= src[i];
    }
}

int main(int argc,char **argv)
{
    int *src = NULL,*dst = NULL;
    int size = 100;
    int i,k;
    src = malloc(size * sizeof(int));
    dst = malloc(size * sizeof(int));
    srand(time(0));
    for(i=0;i<size;i++)
    {
        src[i] = rand() % 100;
    }
    k = 100;//k为这个序列的最大整数加1
    csort(src,dst,size,k);
    printf("src:");
    for(i=0;i<size;i++)
    {
        printf(" %d",src[i]);
    }
    printf(".\n");
    printf("dst:");
    for(i=0;i<size;i++)
    {
        printf(" %d",dst[i]);
    }
    printf(".\n");
}