C++-桶排/箱排

1. 桶排序思路

首先：桶排序是稳定的排序

思想是空间换时间，具体的思路如下：

排序数组1,23,666,333,111,120,999,250,585

1. 首先按照个位数0-9开辟10个和要排序的数组大小相同的数组。

2. 数组的元素按照个位数对应到相应的桶中。

3. 排列完后重新按照顺序写回数组中
   

4. 按照十位数0-9开辟10个大小和待排数组大小相同的数组，按照十位数的0-9对应到相应的数组中。（没有十位数的按照十位数是0来处理）

5. 排列完后重新按照顺序写回数组中
   

6. 因为数组中的元素是3位数，所以还要按照百位0-9重复上面的过程，最后写回数组时数组就有序了
   

2. C++实现桶排序

#include
#include
#include
#include

using namespace std;

#define SORT_NUM 5
#define RANGE 1000

int CoutDigit(int num) {
	int ret = 0;
	while (num) {
		ret += 1;
		num /= 10;
	}
	return ret;
}

void BucketSort(vector<int>&Array) {
	int max_digit = CoutDigit(*max_element(Array.begin(), Array.end()));
	//循环数组元素最大位数次
	int flag = 1;//记录计算到第几位标记
	for (int digit = 1; digit <= max_digit; digit++) {
		// 创建10个箱子, 初始化为 INT_MIN
		vector<vector<int>>Bucket(10, vector<int>(Array.size(), INT_MIN));
		for (int pos = 0; pos < Array.size(); pos++) {
			int idx = (Array[pos] / flag) % 10;//获取对应位的数字
			Bucket[idx][pos] = Array[pos];
		}
		flag *= 10;
		int index = 0;
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < Array.size(); j++) {
				if (Bucket[i][j] != INT_MIN) {
					Array[index++] = Bucket[i][j];
				}
			}
		}
	}
}


int main() {
	srand(time(0));
	vector<int>Array;
	for (int i = 0; i < SORT_NUM; i++) {
		Array.push_back(rand() % RANGE);
		cout << Array[i] << " ";
	}
	cout << endl;
	BucketSort(Array);
	cout << "排序后:" << endl;
	for (auto num : Array) {
		cout << num << " ";
	}
}
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

测试运行结果