排序——基数排序

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(1005);
vector<queue<int> > digitQueue(10);

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (int i = 0; i < n; ++i) {
        os << v[i] << ' ';
    }
    os << endl;

    return os;
}

//根据数字的除以power后的最后一位分桶
void distribute(int power)
{
    for (int i = 0; i < n; ++i) {
        digitQueue[seq[i] / power % 10].push(seq[i]);
    }
}

//将桶内的数字写回原序列
void collect()
{
    int cnt = 0;
    for (int i = 0; i < 10; ++i) {
        while (!digitQueue[i].empty()) {
            seq[cnt++] = digitQueue[i].front();
            digitQueue[i].pop();
        }
    }
}

//基数排序
void radixSort(int d)
{
    int power = 1;
    for (int i = 0; i < d; ++i) {
        distribute(power);
        collect();
        power *= 10;
    }
}

//计算输入的数字的位数
inline int digitCount(int number)
{
    int cnt = 0;
    while (number) {
        number /= 10;
        ++cnt;
    }

    return cnt;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    int d = 0;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i];
        d = max(d, digitCount(seq[i]));
    }
    radixSort(d);
    cout << seq;

    return 0;
}

//测试数据
10
9 66 333 8 55 222 7 44 111 0

两个关键的步骤，分桶distribute，和收集过程collect，额外需要一个digitCount来统计数字的位数。

上面的做法是利用10来进行分桶，但是当数字较大的时候，需要分桶的次数增加，所以一般选择用256来进行分桶，这样整数范围内最多只需要进行三次就可以完成排序，优化了常数。

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(1005), tmp(1005);
vector<int> countNum(256);

void radixSort() {//基数排序
    for (int i = 0; i < 17; i += 8) {//排3次即可
        fill(countNum.begin(), countNum.end(), 0); //每次都要清零
        for (int j = 0; j < n; ++j) ++countNum[(seq[j] >> i) & 255]; //位与上255，相当于对256取余
        for (int j = 1; j < 256; ++j) countNum[j] += countNum[j - 1]; //求前缀和
        for (int j = n - 1; j >= 0; --j) tmp[--countNum[(seq[j] >> i) & 255]] = seq[j];
        for (int j = 0; j < n; ++j) seq[j] = tmp[j]; //数据写回原数组
    }
}

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (int i = 0; i < n; ++i) os << v[i] << ' ';
    os << endl;
    return os;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> seq[i];
    radixSort();
    cout << seq;

    return 0;
}

一个很典型的应用是洛谷-P6033 合并果子 加强版，利用基数排序来实现$O(n)$的排序。