题目描述
给定你一个长度为 $n$ 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 $n$。
第二行包含 $n$ 个整数(所有整数均在 $1 \sim 10^9$ 范围内),表示整个数列。
输出格式
输出共一行,包含 $n$ 个整数,表示排好序的数列。
数据范围
$1 \le n \le 100000$
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
算法
基数排序
网上搜索基数排序C++,大多都是非常低效的实现,于是自己动手实现一个速度较快的版本。
基数排序原理:一图胜千言
在$10$进制下,每次取个位和十位需要用除法和模运算,为了规避除法和模运算,采用$16$进制收集排序。实际测试比快速排序略快(数据量$1e5$较小,出到$1e7$差距会很大)。
自测1e7数据快排需要850ms,而本文章给出的基数排序在16个bucket时为180ms,32bucket为125ms。
时间复杂度 $\Theta (dn)$
最多扫描$d=log_{16}S$轮,$ S=\max\{i\in \left[ 1,N \right] \vert a[i]\} $,每轮收集$n$个元素,故 $\Theta (dn)$
(开$32$个桶比$16$桶更快,不过空间占用会更大)
C++ 过题代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, k, ma, l = 16;
int buck[16][N];
int cnt[16];
void radix_sort(int k){
int mod = 0;
int t, c;
for(int r = 0; r < k; ++ r){
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < n; ++ i){
t = (a[i] >> (mod * 4)) & 15;
buck[t][cnt[t] ++ ] = a[i];
}
mod ++;
for(int i = 0, c = 0; i < l; ++ i)
for(int j = 0; j < cnt[i]; ++ j)
a[c ++] = buck[i][j];
}
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; ++ i){
scanf("%d", &a[i]);
ma = max(ma, a[i]);
}
while(ma > 0){
ma /= l;
k ++;
}
radix_sort(k);
for(int i = 0; i < n; ++ i) printf("%d ", a[i]);
}
时间测试
1.数据生成:注意提前在文件夹下建立in.txt与out.txt
/*
* @Date: 2022-12-26 19:12:54
* @LastEditTime: 2023-01-14 11:19:40
* Bilibili: https://space.bilibili.com/7469540
*/
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <random>
#include <ctime>
using namespace std;
mt19937 rnd(233);
int main() {
#ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
freopen("in.txt", "w", stdout);
#endif
uniform_int_distribution<int> dis(1,1e9);
cout << 10000000 << endl;
for(int i = 0; i < 10000000; ++ i){
printf("%d ", dis(rnd) );
}
return 0;
}
排序时间测试:
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
clock_t start,endt;
const int N = 1e7 + 10;
int a[N], n, k, ma, l = 16;
int buck[16][N];
int cnt[16];
void printt(){
double endtime=(double)(endt-start);
cout<<"Total time:"<<endtime<<"ms"<<endl; //ms为单位
}
void printa(){
for(int i = 0; i < n; ++ i){
printf("%d ", a[i]);
}
puts("");
}
void qsort(int (&a)[N], int l, int r){
if(l >= r) return;
int i = l - 1, j = r + 1, x = a[l+r>>1];
while(i < j){
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
}
qsort(a, l, j);
qsort(a, j+1, r);
}
void radix_sort(int k){
int mod = 0;
int t, c;
for(int r = 0; r < k; ++ r){
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < n; ++ i){
t = (a[i] >> (mod * 4)) & 15;
buck[t][cnt[t] ++ ] = a[i];
}
mod ++;
for(int i = 0, c = 0; i < l; ++ i)
for(int j = 0; j < cnt[i]; ++ j)
a[c ++] = buck[i][j];
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d", &n);
for(int i = 0; i < n; ++ i){
scanf("%d", &a[i]);
ma = max(ma, a[i]);
}
while(ma > 0){
ma /= l;k ++;
}
start=clock();
qsort(a, 0, n - 1);
// radix_sort(k);
endt=clock();
//printa();
printt();
return 0;
}
1e8数据量测试(用快读快写)
1e8数据占了943MB
用快排排序1e8数据,用了11秒(第一个数据是快读时间,不用快读读1e8数据要读上几分钟)
用基数排序1e8数据,只要一秒出头,快10倍!
1e7的数据写出来看看还ok,1e8数据没有什么编辑器不卡死的(也许vim可以?),不建议写。
完整代码:
/*
* @Author: ACCXavier
* @Date: 2021-05-26 21:50:56
* @LastEditTime: 2023-01-14 12:46:16
* Bilibili:https://space.bilibili.com/7469540
*/
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = ' ';
int p, p3 = -1;
void read() {}
void print() {}
inline int getc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline void flush() {
fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
}
template <typename T, typename... T2>
inline void read(T &x, T2 &...oth) {
int f = 0;
x = 0;
char ch = getc();
while (!isdigit(ch)) {
if (ch == '-')
f = 1;
ch = getc();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getc();
}
x = f ? -x : x;
read(oth...);
}
template <typename T, typename... T2>
inline void print(T x, T2... oth) {
if (p3 > 1 << 20)
flush();
if (x < 0)
buf2[++p3] = 45, x = -x;
do {
a[++p] = x % 10 + 48;
} while (x /= 10);
do {
buf2[++p3] = a[p];
} while (--p);
buf2[++p3] = hh;
print(oth...);
}
} // namespace FastIO
#define read FastIO::read
#define print FastIO::print
#define flush FastIO::flush
using namespace std;
clock_t start,endt;
const int N = 1e8 + 10;
const int K = 1.2e7 + 10;
int a[N], n, k, ma, l = 32;
int buck[32][K];
int cnt[32];
void printt(){
double endtime=(double)(endt-start);
cout<<"Total time:"<<endtime<<"ms"<<endl; //ms为单位
}
void printa(){
for(int i = 0; i < n; ++ i){
printf("%d ", a[i]);
}
puts("");
}
void fast_printa(){
for(int i = 0; i < n; ++ i){
print(a[i]);
}
puts("");
}
void qsort(int (&a)[N], int l, int r){
if(l >= r) return;
int i = l - 1, j = r + 1, x = a[l+r>>1];
while(i < j){
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
}
qsort(a, l, j);
qsort(a, j+1, r);
}
void radix_sort(int k){
int mod = 0;
int t, c;
for(int r = 0; r < k; ++ r){
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < n; ++ i){
t = (a[i] >> (mod * 5)) & 31;
buck[t][cnt[t] ++ ] = a[i];
}
mod ++;
for(int i = 0, c = 0; i < l; ++ i)
for(int j = 0; j < cnt[i]; ++ j)
a[c ++] = buck[i][j];
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d", &n);
start = clock();
for(int i = 0; i < n; ++ i){
read(a[i]);
ma = max(ma, a[i]);
}
endt=clock();
printt();
while(ma > 0){
ma /= l;k ++;
}
start=clock();
// sort(a, a + n);
qsort(a, 0, n - 1);
radix_sort(k);
endt=clock();
printt();
start = clock();
// printa();
//fast_printa();
//flush();
endt = clock();
printt();
return 0;
}