Rockdu's Blog

题目描述

利用快速排序算法将读入的N个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）

输入输出格式

输入格式：

输入文件sort.in的第1行为一个正整数N，第2行包含N个空格隔开的正整数a[i]，为你需要进行排序的数，数据保证了A[i]不超过1000000000。

输出格式：

输出文件sort.out将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

5
4 2 4 5 1

1 2 4 4 5

说明

对于20%的数据，有N≤1000；

对于100%的数据，有N≤100000。

今天复习了基数排序，输出优化。基数排序果然很快，只跑了88ms，相比之下sort就上了100ms。另外，基数排序的一些小技巧能让常数变的小得多。代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5;
const int MX = 9; /*排序最大数位*/
int cnt[10], n1[maxn], n2[maxn], org[maxn], n, now[maxn];
int rank[maxn], op[30], tot; 
int ten[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
inline void read(int & x) {
    x = 0;char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
inline void put(int x) {
    tot = 0;
    while(x) op[tot++] = x % 10, x /= 10;
    while(tot--) putchar(op[tot] + '0');
    putchar(' ');
}
int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) read(n1[i]), org[i] = n1[i];
    int *a = n1, *b = n2;
    for(register int j = 1; j <= MX; ++j) {
        memset(cnt, 0, sizeof(cnt));
        for(register int i = 1; i <= n; ++i) ++cnt[now[i] = (a[i] / ten[j - 1]) % 10];
        for(register int i = 1; i <= 9; ++i) cnt[i] += cnt[i - 1];
        for(register int i = n; i >= 1; --i) b[cnt[now[i]]--] = a[i];
        swap(a, b);
    }
    for(register int i = 1; i <= n; ++i) put(a[i]);
    return 0;
}