计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上
时间复杂度：O(max(n,范围))
空间复杂度：O(范围)
稳定性：稳定
优点：计数排序在数据范围集中时，效率很高
缺点：当数列元素不是整数或最大最小值差距过大时，并不适用计数排序

初步实现

void CountSort(int array[], int size) {
    // 找出最大数和最小数，确定序列的范围
    int max = array[0];
    int min = array[0];
    for (int i = 0; i < size; ++i) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    // rang为序列的范围，开辟额外数组，初始化全为0
    int rang = max - min + 1;
    int* countArr = (int*)malloc(sizeof(int) * rang);
    for (int i = 0; i < rang; ++i) {
        countArr[i] = 0;
    }
    // 进行计数
    for (int i = 0; i < size; ++i) {
        countArr[array[i] - min]++;
    }
    // 将序列拷贝回原序列
    int j = 0;
    for (int i = 0; i < rang; ++i) {
        while (countArr[i]--) {
            array[j++] = i + min;
        }
    }
    free(countArr);
}

优化

从功能上看，这段代码只是简单地按照统计数组的下标输出了元素值，并没有真正给原始数列进行排序。如果放在现实业务里，比如给学生的考试分数排序，遇到相同的分数就会分不清谁是谁。我们需要稍微改变之前的逻辑，对统计数组做一下变形

void CountSort(int sortArr[],int array[], int size) {
    // 找出最大数和最小数，确定序列的范围
    int max = array[0];
    int min = array[0];
    for (int i = 0; i < size; ++i) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    // rang为序列的范围，开辟额外数组，初始化全为0
    int rang = max - min + 1;
    int* countArr = (int*)malloc(sizeof(int) * rang);
    for (int i = 0; i < rang; ++i) {
        countArr[i] = 0;
    }
    // 进行计数
    for (int i = 0; i < size; ++i) {
        countArr[array[i] - min]++;
    }
    // 对所有的计数累加   
    for (int i = 1; i < rang; i++) {
        countArr[i] += countArr[i - 1];
    }
    // 倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
    for (int i = size - 1; i >= 0; --i) {
        sortArr[--countArr[array[i] - min]] = array[i];
    }
    free(countArr);
}