算法：桶排序思想 - 计数排序、基数排序、桶排序_适合使用桶计数的场景

一. 计数排序

桶排序的思想

1.1 运用场景

【*】量大但范围最小：既能用数组下标表示（整数） 且 有很多是并列的

• 公司人员年龄：假设年龄在 0 - 60岁；20万人
• 高考成绩：0-750 分；50万人

其他情况不一定比快速排序快。

总结：

• 计数排序是 非比较排序

• 适用于特定问题，也就是对源数据有要求

1.2 主要思想

• 新建一个数组，用于计数。

• 计算取值范围的数。若是公司年龄 则数组个数为：0 - 60 共 61 个，并初始化为 0

• 遍历员工年龄，用年龄当下标，在对应数组位置中 +1。

1.3 代码

1.3.1 数据范围：0 - 60

#include <iostream>
using namespace std;

const int M = 50;
const int scope = 60;

void main()
{
	srand(2000);
	int* arr = new int[M];
	int* count = new int[scope + 1];

	// 初始化数据数组
	for (int i = 0; i < M; i++)	arr[i] = rand() % scope + 1, cout << arr[i] << " ";

	// 初始化计数数组
	for (int i = 0; i < scope + 1; i++)	count[i] = 0;

	// 统计计数
	for (int i = 0; i < M; i++)	count[arr[i]] += 1;

	// 输出数据
	cout << endl;
	for (int i = 0; i < scope + 1; i++) {
		while (count[i]-- > 0)
		{
			cout << i << " ";
		}
	}

	delete[] arr;	arr = NULL;
	delete[] count; count = NULL;
}
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

1