企业官网建设流程全解析

前言

基数排序（radix sort）是一种非比较排序：它不比较元素的大小，而是按「位」逐轮分桶，从最低位到最高位依次处理，最终得到整体有序。对固定宽度的整数，它的复杂度是 O(d(n+b))，d 是位数、b 是基数，与 n log n 的比较排序走了完全不同的路线。

常见的误解有三个。第一，以为基数排序一定比std::sort快——它需要额外空间、需要多轮遍历，只有在键的位数固定且数据量较大时才可能占优，具体差异必须自行测量，不能想当然。第二，以为基数排序可以随意选择分桶方式——每一轮的分桶必须是稳定的，否则高位排好后低位顺序会被打乱。第三，以为它天然支持负数——按无符号位模式排序会把负数排到正数后面，需要先做符号位变换。

本文用基数 256（每次处理一个字节）实现 32 位无符号整数的排序，再扩展到有符号整数，最后讨论复杂度和适用边界。所有代码以 C++17 为准。

一、算法思想

以十进制为例，要排序[170, 45, 75, 90, 802, 24, 2, 66]：

1. 
   
2. 按个位分桶，收集后得到[170, 90, 802, 2, 24, 45, 75, 66]；
3. 
   
4. 按十位分桶，收集后得到[802, 2, 24, 45, 66, 75, 90, 170]；
5. 
   
6. 按百位分桶，收集后得到[2, 24, 45, 66, 75, 90, 170, 802]。
7. 
   

每一轮都建立在前一轮的结果之上，所以每一轮的分桶必须稳定：相同「当前位」的元素，必须保持上一轮结束时的相对顺序。这一点是基数排序正确性的基石。

对二进制数据，把基数取成 256 意味着每轮看 8 位，32 位整数只需 4 轮。基数取 2 的幂有个额外好处：取某一位段可以用移位加掩码，不需要除法或取模。

二、用计数排序完成一轮分桶

每一轮分桶本质上是一次计数排序（counting sort）：统计每个桶有多少元素，算出每个桶的起始下标，再按原顺序把元素放进对应位置。因为是按原顺序扫描、按顺序放置，稳定性自然成立。

// 适用于 C++17
#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>

void radixSort(std::vector<std::uint32_t>& a) {
constexpr int kBits = 8;
constexpr std::uint32_t kMask = 0xFFu;
constexpr int kPasses = 32 / kBits; // 4 轮

std::vector<std::uint32_t> buffer(a.size());

for (int pass = 0; pass < kPasses; ++pass) {
const int shift = pass * kBits;
std::array<std::size_t, 256> count{};

// 1. 统计每个桶的元素个数
for (std::uint32_t v : a) {
++count[(v >> shift) & kMask];
}

// 2. 前缀和：count[i] 变成第 i 个桶的起始下标
std::size_t total = 0;
for (std::size_t& c : count) {
const std::size_t old = c;
c = total;
total += old;
}

// 3. 按原顺序放入缓冲，保证稳定
for (std::uint32_t v : a) {
buffer[count[(v >> shift) & kMask]++] = v;
}

a.swap(buffer);
}
}

几个实现细节：

• 
  
• count用std::size_t而不是int，避免元素个数超过INT_MAX时的溢出。
• 
  
• 前缀和循环里先把旧值存下来再覆盖，因为c既要做累加源，又要写入新值。写成total += c; c = total;就错了——那样c会变成「累计到当前桶的末尾」而不是「起始」。
• 
  
• 第三步的循环里count[...]++是后置自增：先取当前位置写入，再把该桶的写指针后移。
• 
  
• a.swap(buffer)之后，buffer持有的是上一轮的旧数据，下一轮直接覆盖，不需要清零。
• 
  

三、负数与符号位

std::uint32_t的排序解决了无符号情形。有符号整数不能直接按位模式排——负数的最高位是 1，按无符号比较会被当成很大的数，全部排到正数后面。

标准的处理办法是翻转符号位：把每个数异或0x80000000，负数的高位变成 0、非负数的高位变成 1，映射后的无符号顺序就与原来的有符号顺序一致。排完再翻回来。

// 适用于 C++17
#include <cstddef>
#include <cstdint>
#include <vector>

// 此处沿用上一节定义的无符号版本 radixSort
void radixSortSigned(std::vector<std::int32_t>& a) {
std::vector<std::uint32_t> mapped(a.size());
for (std::size_t i = 0; i < a.size(); ++i) {
mapped[i] = static_cast<std::uint32_t>(a[i]) ^ 0x80000000u;
}

radixSort(mapped); // 按无符号排序

for (std::size_t i = 0; i < a.size(); ++i) {
a[i] = static_cast<std::int32_t>(mapped[i] ^ 0x80000000u);
}
}

static_cast<std::uint32_t>(a[i])对负数做的是模 2³² 的转换，标准明确规定结果，不依赖实现。反向转换static_cast<std::int32_t>在 C++20 之前是实现定义行为（implementation-defined），C++20 起有符号整数被规定为补码表示，该转换的结果被明确定义。在只支持补码的平台上，这段代码的行为与预期一致；如果要写完全不依赖实现定义的代码，可以用std::memcpy按位复制，或使用 C++20 的std::bit_cast。

另一种做法是给所有元素加上一个偏移量，让最小值变成 0，排序后再减回去。但这要求事先求出最小值，且偏移后的值不能溢出，处理起来比翻转符号位麻烦。

四、复杂度与适用边界

设元素个数为 n，基数为 b（这里是 256），轮数为 d（这里是 4）：

基数排序的优势来自「不做比较」：当 n 远大于 b^d 时，它避免了 log n 次比较。但它也有明确的代价：需要一份与原数组等大的缓冲区，且对每个元素都要完整扫过 d 轮。元素很少、或者 d 很大（比如 64 位整数需要 8 轮）时，常数开销可能超过收益。

实际工程中，是否使用基数排序应当基于测量：用std::chrono::steady_clock记录排序前后的时间戳，多次运行取中位数，并注意缓存状态、数据分布、编译器优化选项对结果的影响。不要凭「非比较排序一定更快」的印象做决定。

还有一个前提容易被忽略：基数排序要求键可以按固定宽度拆位。字符串、浮点数、自定义结构体都需要额外处理。浮点数可以先把位模式映射成「可按无符号比较」的形式（正数翻转符号位，负数整体取反），但这一步的细节很容易写错，非必要不建议自己实现。

五、完整示例

// 适用于 C++17
#include <array>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

void radixSort(std::vector<std::uint32_t>& a) {
constexpr int kBits = 8;
constexpr std::uint32_t kMask = 0xFFu;
constexpr int kPasses = 32 / kBits;

std::vector<std::uint32_t> buffer(a.size());
for (int pass = 0; pass < kPasses; ++pass) {
const int shift = pass * kBits;
std::array<std::size_t, 256> count{};

for (std::uint32_t v : a) ++count[(v >> shift) & kMask];

std::size_t total = 0;
for (std::size_t& c : count) {
const std::size_t old = c;
c = total;
total += old;
}

for (std::uint32_t v : a) {
buffer[count[(v >> shift) & kMask]++] = v;
}
a.swap(buffer);
}
}

int main() {
std::vector<std::uint32_t> data{170u, 45u, 75u, 90u, 802u, 24u, 2u, 66u};
radixSort(data);

for (std::uint32_t v : data) {
std::cout << v << ' ';
}
std::cout << '\n';
return 0;
}

按标准语义，输出应为升序的2 24 45 66 75 90 170 802。注意buffer的大小与输入相同；如果输入为空，buffer也是空的，四轮循环体内不会写入任何元素，swap也是空操作，行为正确。

常见坑点

1. 分桶不稳定

❌ 每轮把元素按桶分组时使用「头插」或反向扫描。 ✅ 严格按原数组顺序扫描，并按计数得到的起始位置顺序写入。

2. 前缀和写错

❌total += c; c = total;，桶的起始位置变成结束位置。 ✅ 先保存old = c，再c = total; total += old;。

3. 从最高位开始排（MSD）却按 LSD 的方式收集

❌ 高位先排、低位后收，最终顺序完全错乱。 ✅ LSD 基数排序必须从最低位开始；MSD 需要递归分桶，是另一种实现。

4. 有符号数直接按位排序

❌ 把int直接转uint32_t排序，负数全部跑到末尾。 ✅ 先异或0x80000000翻转符号位，排完再翻回来。

5. 复用缓冲区时忘记它保存的是旧数据

❌ 以为swap后buffer已清空，直接在其上累加。 ✅ 每轮都是完整覆盖写入，不依赖缓冲区原有内容。

6. 用int做计数数组

❌ 元素个数超过INT_MAX时计数溢出。 ✅ 计数与下标统一用std::size_t。

7. 轮数算错

❌ 32 位整数按 8 位分桶只跑 3 轮，高 8 位没参与排序。 ✅kPasses = 32 / kBits，确保覆盖全部位。

8. 对浮点数直接套用整数版本

❌ 把float的位模式当无符号整数排序，负数顺序错误。 ✅ 浮点需要专门的位模式映射；不确定时改用比较排序。

总结

基数排序的核心只有两句话：按位分轮，每轮稳定。把计数排序这一轮写对，剩下就是循环。真正决定它是否值得用的，不是理论复杂度，而是数据规模、键宽度和内存预算——这三点应当用测量说话，而不是凭感觉。