rt

这是一个基于计数排序加强的算法

令序列中最大的数为 $m$ 我们将数列中的每个数都除以 $\sqrt m$ ,记录它们的商和余数,作为两个关键字,再进行双关键字排序,先对第二关键字排序,再对第一关键字排序,这样就解决了计数排序数据范围大时 MLE 的问题,代码如下

#include <iostream>
#include <cstdio>
#include <list>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 100;
int p = 0;
int n;
int a[(const int)2e7 + 10];

struct Node
{
    int val;
    Node *nxt = nullptr;
    Node(int x) : val(x) {}
};

class LIST//链表,手打快一点点
{
public:
    Node *head = nullptr;
    Node *tail = nullptr;
    LIST() { head = tail = new Node(0); }
    inline void push_back(int &x)
    {
        tail->nxt = new Node(x);
        tail = tail->nxt;
    }
};

LIST ls1[MAXN]; // 第一次排序
LIST ls2[MAXN]; // 第二次排序

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read(), p = max(p, a[i]);
    p = sqrt(p);
    // 进行第一次排序
    for (int i = 1; i <= n; i++)
        ls1[a[i] % p].push_back(a[i]); // 先对余数进行排序
    for (int i = 0; i < p; i++)
    {
        Node *pt = ls1[i].head->nxt;
        while (pt)
            ls2[pt->val / p].push_back(pt->val), pt = pt->nxt; // 再对商进行排序
    }
    for (int i = 0; i <= p + 1; i++) // 输出排序后的结果
    {
        Node *pt = ls2[i].head->nxt;
        while (pt)
            printf("%d ", pt->val), pt = pt->nxt;
    }
}

但是为什么这个 $O(n+\sqrt m)$ 的算法实际性能比 $O(n \log n)$ 的sort函数要差 10% 左右呢？