排序算法
2026-10-11 22:27:17
发布于：浙江
众所周知：
- 我们学的排序时间复杂度一般是 ;
- 时间复杂度不计常数。
相信以上两点大家都不陌生。
但是，贴主有一天突发奇想：
既然在计算的时候可以忽略常数，那么我可不可以弄一个常数大n小的算法呢？（bushi）
不得不说，贴主真聪明（bushi），接下来是我的思维进程：
1.计算机和2非常有关，所以从2去想；
和2有关的算法有：二分、二进制、分治、双指针、双序列dp（额好像想歪了。。。）
注意到二进制和分治了吗？在这两个里，很容易想到：
- ;
- 可以设置两个数组，一个数组记录这一位为0的情况，反之另一个数组纪录这一位为1的情况，由上证明，最终一定有序；
- 我们只需要一直递归就可以使数组有序！！！
是的，你们的贴主非常开心，还以为自己发现了新算法，于是上网查了一下，发现：
这个知识点好像叫：“二进制基数排序”。。。
但很显然，上面的代码的时间复杂度为 ,这样的时间复杂度显然无法接受。
于是，聪明的作者又想到了好方法：每次直接比较64次，递归没关系（写得了），而且我们非常明白，64显然是一个常数， 优化成了 !!!（大家可以当笑话看，切勿当真）
这就是二进制基数排序，你，看懂了吗？
补一下正经学术贴该有的东西：
二进制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最低）。
- 当前处理位
bit，取数组区间[l, r] - 双指针：左指针找bit位=1的数，右指针找bit位=0的数，交换两者。
- 一轮结束后，区间被切分成两部分：
[l, mid]：该bit为0[mid+1, r]：该bit为1
- 递归处理左区间（bit-1）、递归处理右区间（bit-1）
- 递归终止条件：
l >= r或者bit < 0
⚠️ 注意：负数处理
如果是有符号int，最高位是符号位。排序时要单独处理符号位：符号位1（负数）排在左边，符号位0（正数）放右边，再分别递归。下面代码先写无符号版本，再补充int版本。
三、复杂度分析
- 时间：，B是二进制位数（32/64），和数据范围无关，线性级。
- 空间：递归栈 ；原地版本额外空间很小；如果开辅助数组是 。
优点：不需要计数数组，二进制只有0/1两个桶；
缺点：递归深度等于位数，32位最多递归32层，栈不会爆；但存在大量小数组递归，可以加小数组插入排序优化（cutoff）。
四、完整C++ 原地二进制MSD基数排序（uint32）
#include <iostream>
#include <vector>
#include <cstdint>
using namespace std;
// 原地二进制MSD基数排序，对[l, r]区间，当前处理bit位
void msd_sort(vector<uint32_t>& a, int l, int r, int bit) {
// 递归终止：区间只有一个元素 或者 所有bit处理完
if (l >= r || bit < 0) return;
int i = l, j = r;
uint32_t mask = 1U << bit; // 取出当前bit的掩码
while (i <= j) {
// 左边找bit=1的元素
while (i <= j && !(a[i] & mask)) i++;
// 右边找bit=0的元素
while (i <= j && (a[j] & mask)) j--;
if (i <= j) {
swap(a[i], a[j]);
i++, j--;
}
}
// [l, j] bit=0；[i, r] bit=1，分别递归低位
msd_sort(a, l, j, bit - 1);
msd_sort(a, i, r, bit - 1);
}
// 对外接口：排序uint32数组，从31位最高bit开始
void binary_msd_sort(vector<uint32_t>& a) {
if (!a.empty()) msd_sort(a, 0, a.size()-1, 31);
}
int main() {
vector<uint32_t> arr = {12, 3, 7, 25, 1, 18, 9};
binary_msd_sort(arr);
for (auto x : arr) cout << x << " ";
return 0;
}
有帮助，赞一个