基数排序
Sharpsmile
·
2023-05-03 15:51:57
·
题解
基数排序
一般叫鸡排（
以下称 n 为需要排序的数组长度，V 为值域大小，一般是 10^9 左右。
算法简介
基数排序，是一种基于桶排的排序方式，在对值域不能使用桶排的前提下（这种是常见的），相对于常用传统大值域排序 O(n\log n) 的时间复杂度，基数排序可以在 O((n+c)\log_c V) 的时间复杂度内对一个数组排序，其中 c 是我们选择的基数，一个常数。
算法流程
我们将每个数字视作 c 进制，回想日常生活中我们比较两个数字的方法：先比较位数，再从高顺次比较。
在实现时，比较位数无疑是麻烦的，不如直接将每个数字的位数都视作一个足够大的常数，多余的位补零。
而第二步顺次比较，看起来是从高到低进行比较，实际上我们是从高到低赋关键字，位次越高优先级越高。在鸡排的过程中，我们从小到大比较关键字，每次按照新的关键字更新，当然，在这个过程中，我们需要保证按照这个新的关键字进行排序的时候，排序是稳定的，这样才能保留之前低级关键字的影响。而在最后，我们的影响优先级会正好和我们实现的排序顺序相反（显然越靠后的影响越大），恰符合我们的关键字关系。
而这个关键字稳定排序，我们一般使用桶排来解决，或者说，基排进行 c 进制拆分的目的就是使用桶排。在某次排序中，我们记 p_i 为该层关键字中 i 的出现次数，对 p_i 进行前缀和，得到 s_i=\sum\limits_{1}^{i}p_i 后，显然 [s_{i-1}+1,s_i] 即为该关键字所对应的排名区间，我们只需要按照此次关键字排序之前的顺序按照当前关键字给每个数字赋一个排名即可。
具体的实现，我们可以令 s_i 有意义：当前关键字为 i 的且仅考虑之前关键字的情况下最大的那个数的排名。我们只需按照上次排序的结果倒着扫一遍，每次遇到关键字 i 就把排名赋值，然后将 s_i 减去一即可。
容易发现，这样做的话，只需要进行 O(\log_c V) 次排序即可得到正确答案。每次排序的复杂度是 O(n+c) 的。在使用的时候我们会根据需求选择适当的 c 。
c 的选取
因为前文我们说了，本质上基数排序其实是对数字进行 c 进制拆分后桶排。而进行进制拆分这一步二进制运算无疑有着较大的优势，会降低代码难度。所以大多数时候我们倾向于选择 c=2^k 作为基数。
目前相对常用的是 65536=2^{16}，在 V\leq 4\times 10^9 时，可以在两次桶排之内对数组进行排序，同时空间允许，而且 c 的部分不会对常数造成过大影响。是相对快速的一个基数。
但是在一些强大的玄学硬件优化下（好像是寄存区还是 cache 什么的？），选取 c=256=2^8 有时候会更快，有兴趣了解的朋友可以左转 P4604 挑战 题解区进行了解。
杂项
基数排序不止被用在数字排序上，常见的其他用途有后缀排序什么的，学好基数排序对后面的一些算法的学习有很大的帮助。