首页 > 代码库 > 计数排序（counting-sort）
计数排序（counting-sort）
计数排序是一种稳定的排序算法，它不是比较排序。计数排序是有条件限制的：排序的数必须是n个0到k的数，所以计数排序不适合给字母排序。计数排序时间复杂度：O(n+k)，空间复杂度：O(k)，当k=n时，时间复杂度可以达到O(n)。
计数排序思想：给定一个符合规定的无序数组，先求出这个数组中最大的数，然后开辟一个辅助数组，将无序数组中的数对应到辅助数组中，并计算出每个数出现的次数。再继续从辅助数组中得出到了每个位置，需要排序的数组中的数出现了几次，然后对应的将无序的数组赋值给另一个数组。
排序过程：
A：2 5 3 0 2 3 0 3 c：2 0 2 3 0 1
位置：0 1 2 3 4 5 6 7 位置：0 1 2 3 4 5
c：2 2 4 7 7 8
位置：0 1 2 3 4 5
b： 3 c：2 2 4 6 7 8
位置：0 1 2 3 4 5 6 7 位置：0 1 2 3 4 5
b： 0 3 c：1 2 4 6 7 8
位置：0 1 2 3 4 5 6 7 位置：0 1 2 3 4 5
b： 0 3 3 c：1 2 4 5 7 8
位置：0 1 2 3 4 5 6 7 位置：0 1 2 3 4 5
b：0 0 2 2 3 3 3 5
位置：0 1 2 3 4 5 6 7
示例代码：
#include <stdio.h>#include <stdlib.h>#include <string.h>void CountingSort(int arrayA[], int arrayB[], int n) //进行计数排序{ int max = 0; for(int i = 0; i<n; i++) //找出数组中最大的数 { if(arrayA[i]>max) max = arrayA[i]; } int * arrayC = (int *)malloc(sizeof(int)*(max+1)); //开辟一个数组空间，用来存储各个数出现的次数 memset(arrayC, 0, sizeof(int)*(max+1)); //将开辟的数组进行初始化为0 for(int i = 0; i<n; i++) //计算各个数出现的次数 arrayC[arrayA[i]]++; for(int i = 1; i<=max; i++) //进行次数的累加，以知道到了那个数，出现了几个要排序的数 arrayC[i] += arrayC[i-1]; for(int i = n-1; i>=0; i--) //从高位到低位排序，保证了稳定性 { arrayB[arrayC[arrayA[i]]-1] = arrayA[i]; arrayC[arrayA[i]]--; } free(arrayC); //释放内存}int main(){ int n; int arrayA[100], arrayB[100]; printf("请输入要排序数组的大小："); scanf("%d", &n); printf("请输入数组中各个数：" ); for(int i = 0; i<n; i++) scanf("%d", &arrayA[i]); CountingSort(arrayA, arrayB, n); for(int i = 0; i<n; i++) printf("%d ", arrayB[i]);}