基数排序 (LSD)

Imtking · 2023-05-17 16:49:01 · 个人记录

前置知识：计数排序

介绍

基数排序的复杂度是 O(kn)。

其中 k 代表的是待排序的关键字个数，对于字符串排序而言 k 为 62，自然数则是 k 为 10。

思想

基数排序（LSD）的思想是将所有整数高位补零，以个位、十位、百位、千位，依次为基准进行排序，通常使用计数排序来辅助。 当前位排序时，同一关键字的数据内部是从小到大排列的，因为在上一位排序时，我们已经将数列按照上一位为关键字从小到大排序，这保证了基数排序的正确性。

实现过程

粘一张来自 OI-wiki 的图片方便理解，具体实现在代码里。

P1177 AC CODE

#include <iostream>

using namespace std;

int a[100100], b[10][100100], cnt[10];

int main()
{
    int n, x = 10;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= 9; ++i) // 在本题中 k 的大小为 9 ，进行 9 轮排序
    {
        for (int j = 0; j <= 9; ++j) cnt[j] = 0;
        // 每次排序前要将记录每个关键字数量的 cnt 数组清空
        for (int j = 1; j <= n; ++j)
        {
            int de = (a[j] % x) / (x / 10); // 分离出关键字(0-9)
            b[de][++cnt[de]] = a[j]; // 将每个关键字分到的数据记录
        }
        x = x * 10;
        int tp = 0;
        for (int j = 0; j <= 9; ++j) // 依据关键字顺序来进行排序
        {
            for (int k = 1; k <= cnt[j]; ++k)
            {
                a[++tp] = b[j][k]; // 将原数组覆盖为本轮排序后数组
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << a[i] << " ";
    return 0;
}