1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

template<class T>
class RadixSort {
typedef typename vector<T>::iterator VITE;
    private:
        vector<T>data;
        T base;
        void count_sort(const T exp, T *count, vector<T> *&temp) {
            fill(count, count+base, 0x00);
            for(VITE v=data.begin(); v!=data.end(); ++v) {
                ++count[ (*v/exp)%base ];
            }
            partial_sum(count, count+base, count);
            for(int i=data.size()-1; i!=-1; --i) {
                temp->at(--count[(data.at(i)/exp)%base]) = data.at(i);
            }
            data=*temp;
        }
    public:
        void radix_sort() {
            T maxv=*max_element(data.begin(), data.end());
            vector<T> *temp = new vector<T>(data.size());
            T *count = new T[base];
            for(T v=1; maxv / v > 0; v*=base) count_sort(v, count, temp);
            delete[] count; count=NULL;
            delete temp; temp=NULL;
        }
        inline void push_back(T d) {
            data.push_back(d);
        }
        inline void insert(const VITE b, const VITE l, const VITE r) {
            data.insert(b,l,r);
        }
        inline T get(size_t n) { return data.at(n); }
        RadixSort() {
            this->base=10;
        }
        inline size_t size(void) {
            return data.size();
        }
        inline void clear(void) {
            data.clear();
        }
        RadixSort(T b) {
            this->base = b;
        }
};

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    RadixSort<int> arr(255);
    int N;
    while(cin>>N) {
        for(int i=0; i<N; ++i) {
            int temp; cin>>temp;
            arr.push_back(temp);
        }
        arr.radix_sort();
        cout<<arr.get(0);
        for(int i=1; i!=arr.size(); ++i) cout<<' '<<arr.get(i);
        cout<<'\n';
        arr.clear();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000000
int arr[MAX];

int cmp(const void *a, const void *b) {
    return *(const int*)a - *(const int*)b;
}

int main(void) {
    int n, i;
    while(scanf("%d", &n)!=EOF) {
        for(i=0; i<n; i++)scanf("%d", arr+i);
        qsort(arr,n,sizeof(int),cmp);
        printf("%d",arr[0]);
        for(i=1; i<n; i++)printf(" %d",arr[i]);
        printf("\n");
    }
    return 0;
}