一、算法思想
计数排序是一种非比较排序算法，又称为雀巢原理，是对哈希直接定址法的变形应用。其基本思想就是借助一个辅助空间，将原序列的元素大小与辅助空间的下标相对应，通过对序列进行遍历，元素每出现一次，则对对应下标计数加一，然后再通过对辅助空间的遍历，进行对原序列数据大小的顺序收回。
示例：
但如果元素数据大小都比较大，处于一个较大的数据范围时，比如数据集中于：100-200之间，或者1000-2000之间等，我们若用一个0-最大元素这么大的辅助空间，那么最小元素之前的空间都没有使用，会造成较大的资源浪费，所以在这之前，我们还需对序列进行一次遍历找出最大与最小元素，获取序列范围。
在对序列进行计数排序时，我们只需要借助范围大小的辅助空间即可，那么此时在计算存放时我们也不能直接使用原数据，需要对其先进行减去一个最小值，不然会造成数组越界。之后在回收时，也就需要对其进行加上最小值进行恢复。
示例：
二、代码实现
1.完整代码
#include<stdio.h> #include<assert.h> #include<stdlib.h> void CountSort(int* array, int size);//计数排序 void PrintArray(int* array, int size);//数组打印 void TestCountSort();//测试函数 int main() { TestCountSort(); return 0; } void CountSort(int* array, int size) {//计数排序 //1.获取元素范围 int minValue = array[0];//标记最小元素 int maxValue = array[0];//标记最大元素 for (int i = 0; i < size; i++) { if (array[i] < minValue) { minValue = array[i]; } if (array[i] > maxValue) { maxValue = array[i]; } } //2.计数排序 int range = maxValue - minValue + 1; int* count = (int*)calloc(range, sizeof(array[0]));//申请辅助空间 if (count == NULL) {//申请失败 assert(0); return; } //2.1计数 for (int i = 0; i < size; i++) { count[array[i] - minValue]++;//元素对应count下标，计数加一（减去最小值作为小标，防止越界） } //2.2排序（回收元素） int index = 0; for (int i = 0; i < range; i++) { while (count[i] > 0) {//按照数组下标对元素进行回收 array[index++] = i + minValue;//回收元素，加上计数时减去的最小值 count[i]--;//每回收一个，计数减一 } } //3.回收空间 free(count);//释放辅助空间 } void PrintArray(int* array, int size) {//数组打印 for (int i = 0; i < size; i++) { printf("%d ", array[i]); } } void TestCountSort() {//测试函数 //int array[] = { 1,2,5,0,1,2,8,9,1,0,2,4,7,5,8,0,4,4,5,8,7,9,7,9 }; int array[] = { 101,104,105,103,102,101,106,103,109,106,108,107,108,109,102,104,107,105 }; int length = sizeof(array) / sizeof(array[0]); printf("排序前："); PrintArray(array, length); CountSort(array, length); printf("\n排序后："); PrintArray(array, length); }
2.测试结果
三、性能分析
1.计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2.时间复杂度：O（MAX（N，范围））
3.空间复杂度：O（范围）
————————————————
