AcWing 785. 快速排序
原题链接
简单
作者:
动力春风
,
2021-08-22 21:58:01
,
所有人可见
,
阅读 224
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n;
int q[N], w[N], s[N];
void bucket_sort() {
for (int i = 0; i < n; i ++) s[q[i]] ++;
for (int i = 1; i < N; i ++) s[i] += s[i - 1];
for (int i = n - 1; i >= 0; i --) w[-- s[q[i]]] = q[i];
for (int i = 0; i < n; i ++) q[i] = w[i];
}
// d表示关键字的数量
// r表示进位制的基数
void radix_sort(int d, int r) {
int radix = 1; // 定义一个进制
for (int i = 1; i <= d; i ++) { // 枚举所有关键字
// 清空所有的桶
for (int j = 0; j < r; j ++) s[j] = 0;
// 统计每个桶里有多少个元素
for (int j = 0; j < n; j ++) s[q[j] / radix % r] ++; // 第一次先求个位
// 统计前缀和
for (int j = 1; j < r; j ++) s[j] += s[j - 1];
// 将每个元素从后往前摆
for (int j = n - 1; j >= 0; j --) w[-- s[q[j] / radix % r]] = q[j];
// 将所有元素赋值回q数组
for (int j = 0; j < n; j ++) q[j] = w[j];
// 做完各位做十位,做完十位做百位……
radix *= r;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++) cin >> q[i];
// bucket_sort();
// 以10进制为例
// 最多有10位
radix_sort(10, 10);
for (int i = 0; i < n; i ++) cout << q[i] << ' ';
cout << endl;
return 0;
}
宝宝太厉害害了