首页 > 编程语言 > 详细

模板 - 基数排序

时间:2019-08-20 02:01:21      阅读:131      评论:0      收藏:0      [点我收藏+]

这个是二进制版本的基数排序,输出成bitset方便观察这个过程会好一些。这个MAXK不太清楚应该是怎么样做的,到时候具体分析移位之后的结果比较好。目前看来应该是取最高有效二进制位。在调用的时候和普通的sort一样调用就可以了。但实际上下面的好像有多余的拷贝操作,要是滚动两个数组,或许可以省掉,不过这样要考虑排序次数的奇偶性,一定意义上得不偿失。在排序次数恰好为偶数(MAXK是K的偶数倍)的时候可以考虑卡掉这个常数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;

const int MAXK = 32;
const int K = 4;
const int BASE = 1 << K;
const uint BASEMO = BASE - 1;
int base[BASE];

uint a[105];
uint tmp[105];

void radix_sort(uint *pb, uint *pe) {
    int n = pe - pb;
    for(int k = 0; k < MAXK; k += K) {
        for(int i = 0; i < n; ++i)
            cout << bitset<32>(pb[i]) << endl;
        cout << endl;
        memset(base, 0, sizeof(base));
        for(int i = 0; i < n; ++i)
            base[(pb[i] >> k) & (BASEMO)]++;
        for(int i = 1; i < BASE; ++i)
            base[i] += base[i - 1];
        for(int i = n - 1; i >= 0; --i)
            tmp[--base[(pb[i] >> k) & (BASEMO)]] = pb[i];
        for(int i = n - 1; i >= 0; --i)
            pb[i] = tmp[i];
    }
    for(int i = 0; i < n; ++i)
        cout << bitset<32>(pb[i]) << endl;
    cout << endl;
}

int main() {
#ifdef Inko
    freopen("Inko.in", "r", stdin);
#endif // Inko
    int n = 10;
    for(int i = 1; i <= n; ++i)
        a[i] = (uint)rand() * (uint)rand() * (uint)rand();
    for(int i = 1; i <= n; ++i)
        cout << a[i] << endl;
    radix_sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i)
        cout << a[i] << endl;
}

模板 - 基数排序

原文:https://www.cnblogs.com/Inko/p/11380532.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!