基数排序的可复用实现（C++11/14/17/20）

基数排序，是对整数类型的一种排序方法，有MSD (most significant digit)和LSD (least significant digit)两种。MSD将每个数按照高位分为若干个桶（按照我们常用的十进制，就是0-9，10个桶，这也是“基数”的由来），在每个桶内使用排序算法（如果也是MSD基数排序，就成了递归，出口在最低位），最后按顺序收集每一个桶，收集到的序列就是有序的。如果入桶和收集的过程能保证先入桶的元素先被收集，那么基数排序就是稳定的。 

而LSD则先按照最低位分组，然后按与入桶相同的顺序重新按更高位分组，直到最高位，最后收集到的序列也是有序的，同时也是稳定的。有图比较容易理解，可以参考相关文章。

基数排序的时间复杂度为O(P(N+B))，额外空间复杂度，LSD为O(N+B)（两个临时数组，见下），MSD最坏情况为O(P(N+B))（所有元素都相等，每次递归复制一次），其中P为位数，N为待排元素个数，B为桶的个数。

无论哪种基数排序，自始至终都没有比较过任何两个元素，原理在于整数的离散性。那么，这是不是意味着无法重载 operator< 的类也能用用基数排序呢？当然不能，无法比较的类的对象显然不能表达为整数（否则为什么无法比较），也就不能用基数排序算法。

基数排序的简单实现，可参考中文维基或英文维基，以及其他相关文章。

但是我觉得吧，这些实现都很逊。不要误会，我不是针对哪个实现，我的意思是网上的各个实现都是垃圾。我们学习数据结构与算法的时候，不能忘记我们学习的目的，这些东西最终都是要用到实际开发中去的，而工程中当然不只有算法。作为一个优化合理就能在O(N)时间复杂度的情况下排完序的算法，基数排序的性能在有些情况下会比 std::sort 还要好（比如OJ不给编译器开优化的时候）。本文就是要实现一个优雅的、可复用的基数排序算法。实际上，算法还是基数排序，本文只是给基数排序做了一个好的接口。

回到基数排序的目的。基数排序什么时候可用呢？当每个待排元素可以分解成相同数量的可取有限个离散量的元素时可用，这些元素可取的离散量的数量可以不同。所以，基数排序可以用在很多类型上，实现起来，无非是每一次求当前“位”上的数的算法不同而已。这里的“位”已经是个抽象概念了，指的就是上述可取有限个离散量的元素。排序的每一轮分类时，只要把这些离散量映射到从0开始的连续整数上，然后插入连续存储的表中对应位置的容器中去（这个操作必须是O(1)）。

所以，这个排序的接口应该包含：待排元素范围、迭代深度（对于MSD）或循环次数（对于LSD）、每一轮分类的基数（即基数排序的退化版桶排序中桶的数量），还有一个谓词，它应该接受待排元素和第几轮两个参数，并返回映射结果，范围为[0,基数-1]。理论上每一轮分类的基数可以不同，但是实现起来有些麻烦（实际上是因为我没想到，现在懒得改了），这里简化为所有的基数都相同。

接口长成这样：

1 template <typename It, typename Parser>
2 void radix_sort(It _begin, It _end, int _radix, Parser _parser, int _pass);

对于 It 类型的对象 iter ，[0,_pass)范围内的整数 pass ， _parser 必须可以调用 _parser(*iter, pass) 并返回[0,_radix)范围内的整数

MSD因为需要递归，耗费大量空间，就不去实现了。LSD的实现不太复杂。大体上是先创建两个 _radix 长度的数组，每个元素都是带排序类型的 vector 容器，然后将范围内元素按最低位放到一个数组相应位置的 vector 的末端，之后在两个数组之间分组、收集，最后收集回原来的迭代器范围中。算法实现如下：

 1 #include <vector>
 2 #include <utility>
 3 
 4 template <typename It, typename Parser>
 5 void radix_sort(It _begin, It _end, int _radix, Parser _parser, int _pass)
 6 {
 7     auto begin = _begin;
 8     std::vector<std::vector<std::remove_reference_t<decltype(*_begin)>>> temp0(_radix), temp1(_radix);
 9     auto src = &temp0;
10     auto dst = &temp1;
11     for (; begin != _end; ++begin)
12         (*src)[_parser(*begin, 0)].push_back(*begin);
13     int pass = 1;
14     while (1)
15     {
16         for (const auto& v: *src)
17             for (const auto& i : v)
18                 (*dst)[_parser(i, pass)].push_back(i);
19         if (++pass == _pass)
20             break;
21         std::swap(src, dst);
22         for (auto& v : *dst)
23             v.clear();
24     }
25     for (const auto& v : *dst)
26         for (const auto& i : v)
27         {
28             *_begin = i;
29             ++_begin;
30         }
31 }

注意第8行， decltype(*_begin) 返回的是引用类型，需要用 remove_reference_t<T> 去除引用，也相当于 typename remove_reference<T>::type ，前者需要C++14，后者需要C++11，都在 <type_traits> 中定义。

接口和实现都好了，这个函数如何使用呢？起始和尾后迭代器没什么好说的，STL中遍地都是，两个整数参数也很常规，关键在于 _parser 所属的类怎么写。最简单的，对于 int 类型，或者稍微广泛一些，对于所有内置整数类型，要怎么获得指定位上的数呢？

这还得先看怎么划分“位”。最容易想到的当然是十进制，但最高位取不到0-9，而且各类型的最高位的取值不统一，同时也不能很方便地获得循环次数，还有负数要考虑，又给最高位的问题引入了新的麻烦。计算机是二进制的，以2为基数，上述问题就不存在了，但效率太低。权衡了一下（一拍脑袋决定），我选择以16为基数，以4个bit为一位。

接下来就是负数的问题。想必你学导论或者学C的时候都学过整数的底层表示。对于带符号整数，最高位为0代表这个数为正，否则为负，将这一位取反，则取反后这个数在无符号表示下的值相当于给取反前带符号值加上这一位的权值。两个数同时对最高位取反，前后两数大小关系不变，这就把带符号类型映射到无符号类型上去了，而且这个操作的成本非常低（取反操作用异或实现，而且操作数中有一个是常量，总共只需一句汇编语句）。

对于无符号类型，不需要也不能将最高位取反。那么问题来了，这个函数对象的类肯定是一个模板类，如何知道其模板类型参数是带符号还是无符号类型呢？你当然可以写个声明然后对每一个内置整数类型去特化，但这么暴力的方法我是不允许出现在我的博客里的。给g++加上参数“-std=c++17 -fconcepts”（不要带引号），给MSVC开启最新标准，我们来体验一把C++20中 concept 。请看代码：

 1 #include <type_traits>
 2 
 3 template <typename T>
 4 class IntegerRadixBase
 5 {
 6 public:
 7     static constexpr int bits = 4;
 8     static constexpr int radix = 1 << bits;
 9     static constexpr int pass = sizeof(T) * 8 / bits;
10 };
11 
12 template <typename T>
13 class IntegerRadix;
14 
15 template <typename T> requires std::is_signed_v<T>
16 class IntegerRadix<T> : public IntegerRadixBase<T>
17 {
18 public:
19     using IntegerRadixBase<T>::bits;
20     unsigned operator()(T _value, int _pass)
21     {
22         return ((_value ^ 1 << (sizeof(T) * 8 - 1)) >> (_pass * bits)) & ((1 << bits) - 1);
23     }
24 };
25 
26 template <typename T> requires std::is_unsigned_v<T>
27 class IntegerRadix<T> : public IntegerRadixBase<T>
28 {
29 public:
30     using IntegerRadixBase<T>::bits;
31     unsigned operator()(T _value, int _pass)
32     {
33         return (_value >> (_pass * bits)) & ((1 << bits) - 1);
34     }
35 };

第15行（第26行同理）， template <typename T> requires std::is_signed_v<T> 是对 class IntegerRadix 的特化，并且约束模板参数 T 要使 std::is_signed_v<T> 为 true 。 is_signed_v<T>相当于 is_signed<T>::value ，前者需要C++17（这下我把C++11/14/17/20都凑齐了），后者需要C++11，同样都在 <type_traits>  中定义。

虽然代码里没有出现 concept 这个关键字，但 requires 是和 concept 一起在新标准中加入的，所以上面这段代码算是用上了 concept 吧。

其实 concept 只是语法糖， requires 子句都可以用 std::enable_if_t 代替，比如 template <typename T> requires std::is_signed_v<T> 可以写为 template <typename T, typename = std::enable_if_t<std::is_signed_v<T>>> ，但是，很好看吗？？？尖括号都数不清了！

更多关于 concept 的内容，也许我以后会开一篇专门讲。

回到算法本身。在 return ((_value ^ 1 << (sizeof(T) * 8 - 1)) >> (_pass * bits)) & ((1 << bits) - 1); 这一句中（运算符优先级：乘除>移位>加减>位运算）， sizeof(T) * 8 得到 T 类型的长度， 1 << (sizeof(T) * 8 - 1) 得到最高位为1其余位为0的数字， _value ^ 1 << (sizeof(T) * 8 - 1) 得到 _value 最高位取反的结果， (_value ^ 1 << (sizeof(T) * 8 - 1)) >> (_pass * bits)  将这个数右移使这一次循环所需要的4位在最低的4位上， (1 << bits) - 1 得到一个bit mask，此处值为 0b1111 ，最后 ((_value ^ 1 << (sizeof(T) * 8 - 1)) >> (_pass * bits)) & ((1 << bits) - 1) 获得这4位。无符号版的没有最高位取反这一步，其余相同。

在需要调用基数排序函数的地方，代码应该写成：

1 std::vector<int> data;
2 radix_sort(data.begin(), data.end(), IntegerRadix<int>::radix, IntegerRadix<int>(), IntegerRadix<int>::pass);

可以把上面代码中的 int 换成任意内置整数类型。

这个基数排序函数就到此为止了吗？没有。前面说过，可以转化为整数的，或者可以表示成有限个有限范围的整数的类的对象，都可以用基数排序。

假设我们有一个从C代码中复用来的类：

1 struct Student
2 {
3     char* number;
4     int score;
5 };

其中 number 表示学生学号，是一个十进制下8位数字的C风格字符串， score 的范围为0-660。那么， Student 类的对象就能表示成11个0-9的整数。为了让这个类支持基数排序，我们只需要写一个取相应位上的数的函数就可以了。如果排序的要求是分数从高到低，然后学号从小到大，那么这个函数对象可以实现为：

 1 #include <stdexcept>
 2 
 3 class StudentRadix
 4 {
 5 public:
 6     static constexpr int radix = 10;
 7     static constexpr int pass = 11;
 8     unsigned operator()(const Student& _student, int _pass)
 9     {
10         if (_pass < 8)
11             return _student.number[7 - _pass] - '0';
12         else switch (_pass)
13         {
14         case 8:
15             return 9 - _student.score % 10;
16         case 9:
17             return 9 - _student.score / 10 % 10;
18         case 10:
19             return 9 - _student.score / 100;
20         }
21         throw std::runtime_error("unknown \"pass\" value");
22     }
23 };

因为LSD基数排序是从低位到高位来分组的，所以较早的循环应该取的较次要的位；为了把分数排成降序，所有分数字段上的位都返回被9减去的结果。

同样地，调用处的代码为：

1 std::vector<Student> students;
2 radix_sort(students.begin(), students.end(), StudentRadix::radix, StudentRadix(), StudentRadix::pass);

对于更加简单的类型，比如0-999的整数，调用就更加简单（往往在这种情况下基数排序比时间复杂度为O(nlogn)的排序算法快）：

 1 std::vector<int> data;
 2 radix_sort(data.begin(), data.end(), 10, [](int _value, int _pass) {
 3     switch (_pass)
 4     {
 5         case 0: return _value % 10;
 6         case 1: return _value / 10 % 10;
 7         case 2: return _value / 100;
 8     }
 9     throw std::runtime_error();
10 }, 3);

最后还要说一下，以上接口和实现都还有优化的空间。对于接口，每一轮循环的基数可以不同，接口中可以加入这种考虑；对于实现，在分组与收集的过程中，每一轮循环，每一个元素都被复制了一次，对于涉及到动态内存的类来说，这是很耗时的，可以将基数排序与表排序结合使用来避免。

文章中如有错误请指正，并欢迎补充。