简要步骤

计数排序顾名思义，就是通过对待排序列计数来达到排序的目的。直接上图

因为计数排序针对小范围内的整数效果比较好（能够转化为整数的数据也能适用），

所以将初始序列设定为{0, 1, 5, 2, 4, 2, 3, 4, 1, 2}

性能分析

时间复杂度：O( N+k )，k为整数的范围。但是当满足以下两个条件时为O( N )，分别为1. 输入的线性表的元素属于有限偏序集S；2. 设输入的线性表的长度为N，|S|=k（表示集合S中元素的总数目为k），则k=O( N )。

空间复杂度：需要另外开辟count和temp数组，所以空间复杂度为O( N+k )，k为整数的范围。

稳定性：当从后往前扫描时，计数排序是稳定的。

代码

#include <stdio.h> #include <memory.h> int MaxNum(int arr[], int length) { if(arr == NULL || length <= 0) { printf("输入错误！"); return -1; } int i; int max = arr[0]; for(i = 0; i < length; i++) if(max < arr[i]) max = arr[i]; return max; } /* * 计数排序 */ void CountingSort(int arr[], int length, int maxnum) { if(arr == NULL || length <= 0 || maxnum < 0) { printf("输入错误！"); return; } int temp[length]; int count[maxnum + 1]; memset(count, 0, sizeof(temp)); // for(int t = 0; t <= maxnum; t++) // temp[t] = 0; //i为arr的下标，j为count的下标 int i, j; for(i = 0; i < length; i++) { if(arr[i] < 0) { printf("输入数组中有负数！"); return; } count[arr[i]]++; } //计算小于等于该位数据的个数 for(j = 1; j < maxnum + 1; j++) { count[j] += count[j-1]; } //从后往前扫描可以保证稳定性 for(i = length - 1; i >= 0; i--) { temp[count[arr[i]]-1] = arr[i]; count[arr[i]]--; } for(i = 0; i < length; i++) { arr[i] = temp[i]; } // int k; // for(i = 0, j = 0; j <= maxnum; j++) // for(k = 0; k < temp[j]; k++) // arr[i++] = j; } int main() { int maxnum; int arr[] = {0,1,5,2,4,2,3,4,1,2}; int length = sizeof(arr)/sizeof(arr[0]); maxnum = MaxNum(arr, length); printf("排序前:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } CountingSort(arr, length, maxnum); printf("\n排序后:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } return 0; }