C++编程用桶排序算法：输入n 个0到100之间的整数，由小到大排序输出
C++编程用桶排序算法：输入n 个0到100之间的整数，由小到大排序输出
以下是使用 C++ 编写的桶排序算法实现：
#include <iostream>
#include <vector>
using namespace std;
// 桶排序函数
void bucketSort(vector<int>& arr) {
const int max_num = 100; // 数据的最大值
const int bucket_size = max_num + 1; // 桶的大小
vector<int> buckets(bucket_size, 0); // 初始化桶
// 将元素放入对应的桶中
for (int i = 0; i < arr.size(); i++) {
buckets[arr[i]]++;
}
// 将所有桶中的元素按顺序放回原数组
int arr_index = 0;
for (int i = 0; i < bucket_size; i++) {
while (buckets[i]-- > 0) {
arr[arr_index++] = i;
}
}
}
int main() {
int n;
cout << "请输入数字个数 n：";
cin >> n;
vector<int> arr(n);
cout << "请输入 n 个0到100之间的整数：" << endl;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bucketSort(arr);
cout << "排序后的数组为：" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}该程序首先读入数字个数 n 和 n 个整数，然后使用桶排序算法将这些数排序，最后输出排序后的数组。桶的大小是 101，其中第 i 个桶表示数字 i 出现的次数。算法的时间复杂度为 O(n + k)，其中 k 为桶的大小，因为对每个元素只需要进行一次桶的插入和一次桶的读取，所以该算法的效率很高。
buckets[arr[i]]++;是什么意思 ？为什么要++？
这里的 是将 对应的桶的计数器加 1 的操作。buckets[arr[i]]++arr[i]
在桶排序算法中，我们首先需要确定桶的数量和桶的范围，然后遍历待排序数组中的每个元素，并将它们分别放入对应的桶中。放入桶中的元素可以使用桶的计数器来计数，也可以使用链表或数组等数据结构来存储。
对于每个桶中的元素，我们可以使用插入排序等算法对它们进行排序，然后按照桶的顺序依次将所有桶中的元素合并到一起，即可得到排序后的结果。
因此，在桶排序中，我们需要使用计数器来记录每个桶中元素的数量，这样才能保证在将所有桶中的元素合并时，它们可以按照正确的顺序被输出。在 这行代码中，我们将 对应的桶的计数器加 1，这样就可以记录该桶中元素的数量了。buckets[arr[i]]++arr[i]
buckets[i]-- > 0 是什么意思
在桶排序算法的最后一步，我们需要将所有桶中的元素按照顺序依次放回原数组中。由于每个桶中的元素可能有多个，而且它们的顺序可能不是我们想要的顺序，因此我们需要遍历所有桶中的元素，并按照顺序依次将它们放回原数组中。
在这个过程中，我们需要判断桶中是否还有元素，如果有，则将桶中的第一个元素取出来放回原数组中，并将该桶的计数器减 1。如果桶中还有其它元素，则继续取出第一个元素放回原数组中。直到该桶中没有元素为止。
因此，在 这行代码中，我们首先判断桶 中是否还有元素，如果有，则将桶中的第一个元素取出来放回原数组中，并将该桶的计数器减 1。如果该桶中还有元素，则继续取出第一个元素放回原数组中。直到该桶中没有元素为止。当该桶中的元素都被放回原数组后，我们就可以继续遍历下一个桶，直到所有桶中的元素都被放回原数组为止。while (buckets[i]-- > 0)
代码中没用 #include <vector> 实现的程序：
#include <iostream>
#include <cstring>
const int MAX_N = 100;
void bucket_sort(int arr[], int n) {
int buckets[MAX_N + 1]; // 桶数组
memset(buckets, 0, sizeof(buckets)); // 将桶数组全部初始化为 0
for (int i = 0; i < n; i++) {
buckets[arr[i]]++; // 将元素放入对应的桶中
}
int arr_index = 0;
for (int i = 0; i <= MAX_N; i++) {
while (buckets[i]-- > 0) { // 将桶中元素按顺序放回原数组
arr[arr_index++] = i;
}
}
}
int main() {
int n;
std::cout << "请输入数组长度：";
std::cin >> n;
int arr[n];
std::cout << "请输入" << n << "个0到100之间的整数：" << std::endl;
for (int i = 0; i < n; i++) {
std::cin >> arr[i];
}
bucket_sort(arr, n); // 进行桶排序
std::cout << "排序后的数组为：";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}该代码使用一个长度为101的桶数组，下标代表元素值，值代表元素出现次数。首先将数组中的元素按照出现次数放入对应的桶中，然后按顺序将桶中的元素放回原数组。最终实现了对给定整数范围内的整数进行排序的功能。
