C语言计数排序

假如对某个字节数组排序(每个元素为unsigned char)，数组内容为：

 我们要求把上述数组按从小到大排序，相同大小的元素按在数组中索引排序。最终结果的序号从1开始，也就是比如最终排序好的数组为res，那排在第一的元素放在res[1]里，而不是res[0]里。

计数排序的思路是：

先确定待排序序列中，每个大小不同的数字从小到大各有几个，拿上面的序列来说，有3种大小不同的数字，分别是10、97、98，他们各有1个、5个、3个。这一步是为了下一步累加做准备。

那又为什么需要累加呢？

先看怎么累加，我们把每种不同的数字的个数累加，分别得到1、6、9，它们分别代表：

所有值为10的字节中，在最终的排序结果里面，排在最后一个的序号是1！

所有值为97的字节中，在最终的排序结果里面，排在最后一个的序号是6！

所有值为98的字节中，在最终的排序结果里面，排在最后一个的序号是9！

这就是累加的意义。

因为确定了这一步，我们可以得到上述序列中，排在第1的是10，排在第2~6的是97，排在第7~9的是98。也就是我们先确定了每种大小不同数字的排序范围！然后我们再把都是97的第2到第6按他们在数组内的索引(即出现的先后顺序)排序，所得到的序列就是排序的最终结果。

用图像表示就是：

看到上图你应该明白，最终序列第几个是大小多大的数字我们已经确定了，但是它在原始序列中的位置我们并不知道。就比如上图中排在第4的肯定是97，但是原来序列中有5个97，他们的索引分别是0、3、4、5、7，那排在第4的97的索引还需要我们进一步排序。

所以接下来再根据原始序列去排序，这里有两种排序方法，但其实没什么区别，一种是从每种数字的第一个开始排(即按顺序)，一种是从每种数字的最后一个开始排(即按逆序)。

逆序排序的思想就是之前讲为什么累加的那段标红的描述，比如：

所有值为97的字节中，在最终的排序结果里面，排在最后一个的序号是6！

按照顺序排序思想，这段话可以被重新解读为：

所有值为98的字节中，在最终的排序结果里面，排在第一个的序号是7！

需要注意的是，因为值为10的数字累加后只有一个，证明没有比它更小的数字了，所以所有值为10的字节中，在最终的排序结果里面，排在第一个的序号是1。

所谓的顺序排序，即按顺序历遍原始序列，把每种数字按顺序分配到每种数字的范围内。听起来有点拗口，按上面的例子，比如我们从第一个元素'a'开始，它在最终排序结果里面，起始序号是2，这个已经由前面的累加计算出来了，那我们就把它的序号分配为2，这就是它的最终排序序号。

假如我们循环到第3个字节也是'a'，因为它所处范围2~6中，2这个序号已经被分配掉了，所以给它序号分配为3。其他同理。

后面的排序图片不再赘述，是不是很简单？第二步排序归纳起来就是4个字：先来后到 ！把原始序列的所有数字按顺序再放到它们对应的范围内即可。

把上面的思路倒过来，我们从后往前分配，把每种数字都分配到它所在范围的最后一个序号即可。

按照我们的思路，第一步计算每种数字的个数，注意，此处笔者规定了这是一个字节数组排序，所以我们认为每个元素是unsigned char类型，取值在0~255之间。

我们先计算每种数字有几个：

void CountingSort(unsigned char *ary,int size)
{
    int count[256] = {0};
    int i;
    for(i=0;i

void CountingSort(unsigned char *ary,unsigned char *sary,int size)
{
    int count[256] = {0};
    int i;
    for(i=0;i

void CountingSort(unsigned char *ary,unsigned char *sary,int size)
{
    int count[256] = {0};
    int i;
    for(i=0;i=0;--i)
        sary[count[ary[i]]--] = ary[i];
    //顺序
    // for(i=0;i

int main(int argc, char **argv)
{
    unsigned char ary[] = "abbaaaba\n";//注意结尾''不计算在内
    unsigned char sary[sizeof(ary)] = {0};
    CountingSort(ary,sary,sizeof(ary)-1);
    for(int i=1;i