「洛谷日报第15期」基数排序——你值得拥有

前言

　　随着算法竞赛的发展，它对算法解决问题的能力要求更高，同时要求选手不断进行创新优化以及突破，并且要求算法具有一定的”通用性“，不能适应应用环境的算法终将渐渐淡出视野。因此研究一些并不是常用的算法也是比较重要的，特别是该算法在算法竞赛中体现出了实用性以及对陈旧的解法的突破。一个比较基础的算法——基数排序便是如此，本文便是在介绍基数排序的基础上尝试加以优化的同时提高”通用性“。

引入

　　我们知道“基于交换的排序算法时间复杂度下限是”（可以简单地理解为给定序列的排列方式有种，然后我们每次进行一次交换最多可以排除掉一半的序列，最后复杂度相当于（斯特林公式可求））。
　　但是现实中算法总会有常数，而且快速排序会被卡（C++对sort的优化还可以，例如根据数据特征判断不同时候的方法等等），一般情况下stable_sort采用的是归并排序和插入排序（详见STL源码），其实效率有时还会高一些。

桶排序

　　但是如果希望一个的排序怎么办？我们学习过一个传统的桶排序，这里稍微介绍一下桶排序，时间复杂度为。

　　桶排序的原理是按照值把待排序的分类并且存入容器中，然后顺序扫描容器，就可以按照顺序得到所有元素，例如

单关键字排序

　　在下一节准备了一份样例代码。

桶排序的多关键字排序

　　桶排序如何做多关键字排序？这对于我们的基数排序算法十分重要。桶排序的多关键字排序主要依赖于反复颠倒排名与位置的关系，也就是这样的一张图：

双关键字排序

　　同时建议阅读下面的注释辅助和下面的解释食用。

　　为什么d[e[i].y]] --可以取得排名对应的呢？首先考虑到我前面统计的d长什么样子。首先d作为桶有值的地方都++，然后在统计了一发前缀和，于是得到的就是在没有重复的情况下得到的排名，然后每次遇到一次e[i].y的时候d--，然后就把同一个数分配了几个不同的排名，例如我第一次遇到9的时候排名是8，第二次遇到的时候就是7了。但是注意我们分配排名的时候是递减的
　　然后第二次a[c[e[b[i]].x] --] = b[i]的时候我们的循环倒序枚举的是排名，首先最里层将取出排名为i的第二关键字的位置，然后向外一层取出该位置的第一关键字的值，然后再向外一层取出第一关键字的值的排名，同时注意到第一关键字相同但是第二关键字靠后的将会在靠前的次序取出，这个时候分配的第一关键字靠后，于是完成了排序。
　　对于多层排序的分析也就像上面一样一层层解析数组即可。

基数排序

　　我们发现，如果我有一个非常大的元素需要排序的话那么这个桶是存不下的，同时最大的元素大了之后扫描桶的时间复杂度非常高。
　　所以如何优化这个东西呢？于是就有基数排序。
　　标准的基数排序每次从小到大排序十进制下的一个位，并且只关心这一个位，例如下图

　　为什么要从低位到高位排：首先是为了保证相同高位的数字可以能够按照低位排序，而且如果高位优先，那么高位排好的序在低位又会被打乱。

优化的基数排序

　　　注意到上面操作用的时间是(n + log_{10}(Max\{val[i]\})) * (log_{10}(Max\{val[i]\}))(n+log10(Max{val[i]}))?(log10(Max{val[i]}))，简写为O(nlog_rm)O(nlogrm)，其中nn为元素个数,rr是排序所用的基数，mm为所有元素最大值的大小。
　　但是一般的log_rmlogrm接近10，而且还涉及到取模等操作，速度略慢，常数较大。
　　所以我们考虑一下以二的幂次为基数的排序，首先一个比较好的优点应该是它的几乎所有操作都可以围绕二进制操作，常数小，然后再一个就是如果以2^8=256=0×ff+128=256=0×ff+1为一个基数的话,那么int范围内的log_rmlogrm只有4，然后255的数组还可能可以写入内存而不是硬盘（也有可能写入缓存）。
　　于是我们发现以二的幂次为基数的二进制基数排序是我们所需要的，而且效果也比较优秀，至少目前Luogu1177快速排序的某个匿名者用的是这个优化，效果便是目前的16ms的排序（当然我们可以确信它可以做得更好）。
　　这张图描述了一次这样的排序。

优化的基数排序

一个扩展的功能

　　同时我们有时候还会有一个对于结构体进行多关键字排序的需求，我们注意到C++内定的数据类型至少为1个字节，一般用的整数为4个字节，然后我们发现对于一个32为整数k，我们对k进行32为的比较可以认为是先进行16位高位的比较然后再进行16位的低位的比较，在高位相等的时候比较低位，这不就是双关键字排序吗？
　　于是结构体的双关键字排序可以这样做：先利用指针类型转换结构体成为32/64位整数，然后再适当调整基数直接排序这些整数，然后就可以得到这些排序后的结构体。
　　结构体的内存分布如下：

一个结构体
　　对于这个结构体，使用64位排序，基数2^{16}216（2^828也行）

实现方法

这里直接以template作为参数进行32位排序，这个参数接受不高于32位的类型。a为待排序数组，b为临时数组
　　现在看看代码如何写。

1、首先开四个数组作为4个关键字的桶（基数为2^828）

2、把元素用二进制运算拆开，放入桶内

3、桶子进行桶排序，利用上一次排序的结果交替利用数组进行下一次排序

　　注意结构体排序的待排序关键字应该定义在结构体的前面（和内存有关），不建议使用union。同时在以前所有r数组开的都是0xff的大小,但是后来考虑到实际使用的时候不同的机子或不同的时间下有不同的内存情况,所以后来把数组扩大了1(测试过不会导致缓存反复重写的问题).

使用实例

　　Luogu P2672 推销员
　　这是一道贪心题，思路比较微妙：

注意到对于答案的贡献是，但是对答案的贡献是
分析对于推销个人答案的组成：要么答案就是由值最大的个人构成，要么答案是由值最大的个人和一个非常大的人构成

　　这里对于排序的需求是对于结构体储存的a,s基于a的单关键字排序。
　　然后这里使用基数排序优化常数，目前Rank1。

课后思考

　　我在上一份代码中间留下了一个瑕疵：我首先对data数组进行了从小到大的排序，然后再通过swap调换顺序。那么如何修改基数排序使其资瓷从大到小的排序呢？请思考。

写在最后

　　其实学习基数排序会比较实用，至少理解了这个之后就可以对后缀数组的倍增求法的理解有大大的长进。
　　然后绘图工具：GraphViz和Sequence Diagrams。
　　参考不少博客（在此不一一列出）和《算法导论》对基于交换的排序算法的下限的分析。

　　所有算法都有其存在的意义与价值。

本文发布于洛谷日报，特约作者：Creeper_LKF

原文地址：https://www.luogu.org/blog/CreeperLKF/Radix-Sort