计数排序是一种非比较的排序算法
优势：
计数排序在对于一定范围内的整数排序时，时间复杂度为O(N+K) （K为整数在范围）快于任何比较排序算法，因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N))。
缺点：
计数排序是一种牺牲空间换取时间的做法，并且当K足够大时O（K）>O(N*log(N)),效率反而不如比较的排序算法。并且只能用于对无符号整形排序。
时间复杂度：
O（N） K足够大时为O（K）
空间复杂度：
O（最大数-最小数）
性能：
计数排序是一种稳定排序
代码实现：
|
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
|
#include <iostream>
#include <Windows.h>
#include <assert.h>
using namespace std;
//计数排序，适用于无符号整形
void CountSort(int* a, size_t size)
{
assert(a);
size_t max = a[0];
size_t min = a[0];
for (size_t i = 0; i < size; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
size_t range = max - min + 1; //要开辟的数组范围
size_t* count = new size_t[range];
memset(count, 0, sizeof(size_t)*range); //初始化为0
//统计每个数出现的次数
for (size_t i = 0; i < size; ++i) //从原数组中取数，原数组个数为size
{
count[a[i]-min]++;
}
//写回到原数组
size_t index = 0;
for (size_t i = 0; i < range; ++i) //从开辟的数组中读取，开辟的数组大小为range
{
while (count[i]--)
{
a[index++] = i + min;
}
}
delete[] count;
}
void Print(int* a, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
cout << a[i] << " ";
}
cout << endl;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include "CountSort.h"
void TestCountSort()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 4, 5, 8, 9, 5, 11, 11, 22, 12, 12 };
size_t size = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, size);
Print(arr, size);
}
int main()
{
TestCountSort();
system("pause");
return 0;
}
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！