递归式学习3

松氏基排

基数排序

基数排序（Radix sort）是一种非比较型的排序算法，它的工作原理是将待排序的元素拆分为 $k$ 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 $k$ 关键字进行稳定排序，再对第 $k - 1$ 关键字进行稳定排序，再对第 $k - 2$ 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序

如图，要对这些数字排序，我们以百位为第一关键字，十位为第二关键字，个位为第三关键字

先用第三关键字（个位）稳定排序，再用十位、百位，最后就得出答案

基数排序需要借助一种稳定算法完成内层对关键字的排序，一般是桶排

当然，一般来说可不会以 $10$ 为基数，因为这样一个 int 要排 $9$ 遍，太麻烦

松式基排

那基数取多少好呢？

一般基排取的是 $65536$ （ $2^{16}$ ），空间开的下，只用排两遍

可wys大佬说，取 $256$ ，用位运算把一个数拆成四部分，要排四遍，但这样的话 cnt 数组刚好能装进 $L1$ 高速缓存（我也不知道那是啥）

代码

#include <bits/stdc++.h>
#define STC static
#define geted(x, d) (((x) >> ((d) * Bit)) & (R - 1))
using namespace std;
const int N = 1e5 + 5;
const int Bit = 8, R = 256;
int n, a[N];
void radix_sort()
{
    STC int cnt[R], t[N];
    int *x = a, *y = t;
    for (int d = 0; d < 4; ++d)
    {
        for (int i = 0; i < R; ++i)
            cnt[i] = 0;
        for (int i = 0; i < n; ++i)
            ++cnt[geted(x[i], d)];
        for (int i = 1; i < R; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i)
            y[--cnt[geted(x[i], d)]] = x[i];
        swap(x, y);
    }
    for (int i = 0; i < n; ++i)
        a[i] = x[i];
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    radix_sort();
    for (int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    return 0;
}