众所周知：
1. 我们学的排序时间复杂度一般是 O(nlogn)或O(n2)O(n \log n) 或 O(n^2)O(nlogn)或O(n2);
2. 时间复杂度不计常数。
相信以上两点大家都不陌生。
但是，贴主有一天突发奇想：
既然在计算的时候可以忽略常数，那么我可不可以弄一个常数大N小的算法呢？（BUSHI）
不得不说，贴主真聪明（bushi），接下来是我的思维进程：
1.计算机和2非常有关，所以从2去想；
和2有关的算法有：二分、二进制、分治、双指针、双序列dp（额好像想歪了。。。）
注意到二进制和分治了吗？在这两个里，很容易想到：
1. 前k位全是1一定小于第k+1的一个1前 k 位 全是 1 一定小于 第 k + 1 的一个1前k位全是1一定小于第k+1的一个1 ;
2. 可以设置两个数组，一个数组记录这一位为0的情况，反之另一个数组纪录这一位为1的情况，由上证明，最终一定有序；
3. 我们只需要一直递归就可以使数组有序！！！
是的，你们的贴主非常开心，还以为自己发现了新算法，于是上网查了一下，发现：
这个知识点好像叫：“二进制基数排序”。。。
但很显然，上面的代码的时间复杂度为 O(nlogmaxi=1nai)O(n \log \max_{i = 1}^{n} a_i)O(nlogmaxi=1n ai ),这样的时间复杂度显然无法接受。
于是，聪明的作者又想到了好方法：每次直接比较64次，递归没关系（写得了），而且我们非常明白，64显然是一个常数，O(nlogmaxi=1nai)O(n \log \max_{i = 1}^{n} a_i )O(nlogmaxi=1n ai ) 优化成了 O(n)O(n)O(n) !!!（大家可以当笑话看，切勿当真）
这就是二进制基数排序，你，看懂了吗？
补一下正经学术贴该有的东西：
二进制MSD基数排序详解 + C++实现
> MSD：Most Significant Digit，高位优先基数排序。
> 二进制MSD基数排序：按二进制位从高位到低位依次划分，不是从最低位（LSD）。
> 核心思想：从最高二进制位开始，把数组分成「当前位为0」和「当前位为1」两组；递归对两组继续低位划分，直到所有位处理完毕或子数组长度≤1。
一、MSD VS LSD 基数排序
项目 LSD（低位优先） MSD（高位优先） 遍历顺序 从最低位 → 高位 从最高位 → 最低位 特点 稳定，适合固定长度数字，迭代实现 分治递归，类似快速排序；天然不稳定 二进制场景 先排bit0，再bit1... 先排最高bit，再往下递归
> ⚠️ 二进制MSD本质是按bit分桶的分治算法，每次只分两个桶（bit=0 / bit=1），所以也叫二进制快速基数排序。
二、原理详解
假设数字是32位无符号整数，最高位是第31位（从0开始计数，bit0最低）。
1. 当前处理位 bit，取数组区间 [l, r]
2. 双指针：左指针找bit位=1的数，右指针找bit位=0的数，交换两者。
3. 一轮结束后，区间被切分成两部分：
* [l, mid]：该bit为0
* [mid+1, r]：该bit为1
4. 递归处理左区间（bit-1）、递归处理右区间（bit-1）
5. 递归终止条件：l >= r 或者 bit < 0
> ⚠️ 注意：负数处理
> 如果是有符号int，最高位是符号位。排序时要单独处理符号位：符号位1（负数）排在左边，符号位0（正数）放右边，再分别递归。下面代码先写无符号版本，再补充int版本。
三、复杂度分析
* 时间：O(n⋅B)O(n \cdot B)O(n⋅B)，B是二进制位数（32/64），和数据范围无关，线性级。
* 空间：递归栈 O(B)O(B)O(B)；原地版本额外空间很小；如果开辅助数组是 O(n)O(n)O(n)。
> 优点：不需要计数数组，二进制只有0/1两个桶；
> 缺点：递归深度等于位数，32位最多递归32层，栈不会爆；但存在大量小数组递归，可以加小数组插入排序优化（cutoff）。
四、完整C++ 原地二进制MSD基数排序（UINT32）
有错轻喷，问题私信，谢谢！！！
@cjdst
@wcqk🦐
@异雷
帮我看两眼，谢谢 大佬！！！
