计数排序是一种非比较类型的排序算法，时间复杂度可以达到O(n)，但需要额外的辅助空间
计数排序需要保证数据input[i]在一定范围内，如0~k，则可以额外创建k大小的数组hash[i]，对于输入数据不进行比较，而是计数每个数据出现的次数，保存在hash[input[i]中
然后根据hash中的计数次数，将对应数值填入输出中，如hash中的数据为1，0，3，2，0，则表示输入中有1个0，0个1，3个2，2个3，0个4，则输出为0，2，2，2，3，3
为了实现稳定排序，可以计算hash中每个元素的前缀和，从后往前遍历input[i]，并将其填入hash[input[i]]的位置(hash中现在保存的是前缀和)，然后hash[input[i]]–

#include<stdio.h>
#include<stdlib.h>
#define ARRAY_SIZE 9

void countSort(int *input, int size)
{
        /* 假装输入只有0到100 */
        int hash[100] = {0};
        int *output = NULL;
        int i = 0;
        int index = 0;

        if (!input)
        {
                return;
        }

        output = (int *)malloc(sizeof(int) * size);
        if (!output)
        {
                return;
        }

        /* 统计各个数据出现次数 */
        for (i = 0; i < size; i++)
        {
                hash[input[i]]++;
        }

        /* 计算前缀和 */
        for (i = 1; i < 100; i++)
        {
                hash[i] += hash[i - 1];
        }

        /* 从后往前遍历输入，将它们放入output中 */
        for (i = size - 1; i >=0; i--)
        {
                index = hash[input[i]] - 1;
                output[index] = input[i];
                hash[input[i]]--;

        }

        for (i = 0; i < size; i++)
        {
                input[i] = output[i];
        }

        free(output);
}

int main(void)
{
        int i = 0;
        int array[ARRAY_SIZE] = {38, 22, 3, 1, 29, 4, 58, 52, 6};

        countSort(array, ARRAY_SIZE);

        for (i = 0; i < ARRAY_SIZE; i++)
        {
                printf("%d ", array[i]);
        }

        puts("");

        return 0;
}

O(n)

取决于输入数据范围d，O(d)

输入数据要在一定范围内