【题目来源】https://oj.czos.cn/p/1010【题目描述】对数组的元素按从小到大进行排序。【输入格式】第一行有一个整数 n5≤n≤10第二行有 n 个整数每个整数的值在 [0,10^9]的范围内。【输出格式】输出排序后的数组。【输入样例】81 2 3 6 8 7 4 5【输出样例】1 2 3 4 5 6 7 8【数据范围】5≤n≤10【算法分析】● 桶排序https://oi-wiki.org/basic/bucket-sort/桶数优先选 10、20、100或等于元素个数 n。值域超大1e5、1e9时固定桶数为 50~100即桶数不随着值域变化。gap(最大值一最小值)桶数量。● 严谨来说如下“桶排序”的代码是有 bug 的。即一维数组一旦开到本题所需的 1e9 的水准必然内存溢出报错。但测试时取 N1e35也通过了。#include bits/stdc.h using namespace std; const int N1e35; int a[N]; int n,x; int main() { cinn; for(int i1; in; i) { cinx; a[x]; } for(int i1; iN; i) { while(a[i]) { couti ; a[i]--; } } return 0; } /* in: 5 6 9 2 7 1 out: 1 2 6 7 9 */故考虑利用动态数组 vector 进行优化。【算法代码桶排序】#include bits/stdc.h using namespace std; const int bkt_num10; vectorint bkt[bkt_num]; int n,x; int main() { cinn; int gap100; for(int i0; in; i) { cinx; int idx/gap; bkt[id].push_back(x); } for(int i0; ibkt_num; i) { sort(bkt[i].begin(),bkt[i].end()); for(int x:bkt[i]) { coutx ; } } return 0; } /* in: 5 6 9 2 7 1 out: 1 2 6 7 9 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161347829https://blog.csdn.net/hnjzsyjyj/article/details/161332702https://blog.csdn.net/hnjzsyjyj/article/details/161346075https://blog.csdn.net/hnjzsyjyj/article/details/161588834https://blog.csdn.net/hnjzsyjyj/article/details/119820490https://blog.csdn.net/hnjzsyjyj/article/details/119819927