计数排序
举个栗子来理解计数排序，输入数组arr[5] = {3, 4, 3, 2, 1}进行计数排序，会输出{1, 2, 3, 3, 4}。这个算法由以下步骤组成：
初始化计数数组count[size]，数组大小为数组中size = 最大值 - 最小值 + 1- 统计arr数组中每个值为
k的元素出现的次数，存入计数数组count的第k项(此处为了节约开辟的数组空间，可以存入数组的k-min项) - 遍历整个计数数组，将count中
大于0的数对应原数组的值写回原数组中
例子:
输入arr[5] = {3, 4, 3, 2, 1}
实现步骤1最大元素max = 4， 最小min = 1,开辟计数数组count[size] ,size = max - min + 1 = 4
初始化count[4] = {0, 0, 0, 0}
实现步骤2，计算出arr中元素对应在count中的出现的次数
{3, 4, 3, 2, 1} -> {0, 0, 1, 0} (值为3的元素，在count的第3-min项，即第2项，从0开始算)
{3, 4, 3, 2, 1} -> {0, 0, 1, 1}
{3, 4, 3, 2, 1} -> {0, 0, 2, 1}
{3, 4, 3, 2, 1} -> {0, 1, 2, 1}
{3, 4, 3, 2, 1} -> {1, 1, 2, 1}
实现步骤3
{1, 1, 2, 1} -> {1, 4, 3, 2, 1}(下标:0+min:1即为对应原数组的值)
{0, 1, 2, 1} -> {1, 2, 3, 2, 1}
{0, 0, 2, 1} -> {1, 2, 3, 2, 1}
{0, 0, 1, 1} -> {1, 2, 3, 3, 1}
{0, 0, 0, 1} -> {1, 2, 3, 3, 4}
{0, 0, 0, 0} -> {1, 2, 3, 3, 4}
CountSort.c源码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <stdio.h>
#include <stdlib.h>
void printArray(int *arr, int n)
{
int i;
for (i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void countSort(int * arr, int n)
{
int max = arr[0], min = arr[0],i;
// 找出数组中的最大值 最小值
for (i = 0; i < n; ++i)
{
if (arr[i] < min){
min = arr[i]; // 更新最小值
}
if (arr[i] > max) {
max = arr[i]; // 更新最大值
}
}
int size = max - min + 1; // 计数数组count的大小
int *count = (int *) malloc(sizeof(int) * size);
for (i = 0; i< size;++i)
{
count[i] = 0; // 初始化count
}
// 将arr[]对应的数放入统计数组中 arr[i]-min对应的偏移量
for (i = 0; i< n; ++i)
{
count[arr[i] - min]++;
}
// 遍历哈希表，将count数组中大于0的数对应出原数组的值，
int j = 0;
for (i = 0; i < size; ++i)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
}
int main(void)
{
int arr[5] = {3,4,3,2,1};
countSort(arr,5);
printArray(arr, 5);
return 0;
}
总结
时间复杂度: O(N + k)，n是输入数组长度，k是最大的数的大小。
空间复杂度: O(N + k)，n是输入数组长度，k是最大的数的大小
优点：
- 无需进行比较，所以时间上快于任何的比较排序。
- 适用于数据比较
集中,规模小的数据排序
缺点：
- 计数排序对于数据
范围很大的数组，需要大量时间和内存 - 必须是
正整数
pS:源代码链接