Closer's Space

梦河之上, 一叶扁舟

基数排序


基于桶排序思想

#include <bits/stdc++.h>
using namespace std;
int debug = 0;
#define Debug cout << "Debug: " << ++debug << endl;
int elem[110];
int N;
int weight[] = {1, 10, 100, 1000, 10000};
int bucket[10][110];

void read(){
        cin >> N;
        for(int i = 1; i <= N; ++i)
                cin >> elem[i];
}

void output(){
        for(int i = 1; i <= N; ++i)
                cout << elem[i] << ' ';
        cout << endl;
}

int getDigit(int x, int d){
        return x / weight[d] % 10;
}

void bucketSort(int a[], int l, int r){
        for(int i = 0; i < 5; ++i){
                for(int j = 1; j <= N; ++j){
                        int curCnt = getDigit(a[j], i);
                        bucket[curCnt][0]++;
                        bucket[curCnt][bucket[curCnt][0]] = a[j];
                }
                for(int k = 0, j = 0; j < 10; ++j){
                        for(int d = 1; d <= bucket[j][0]; ++d)
                                a[++k] = bucket[j][d];
                        bucket[j][0] = 0;
                }
        }
}

int main(){
        freopen("in.txt", "r", stdin);
        read();
        bucketSort(elem, 1, N);
        output();
        return 0;
}

博文最后更新时间:


评论

  • 暂无评论

发表评论

来访统计

访问量:144

评论总数:0