1. 基数排序算法深度解析

1.1 算法原理与核心思想

基数排序是一种非比较型整数排序算法，它彻底颠覆了传统比较排序（如快速排序、归并排序）的思维方式。想象一下邮局分拣信件的过程：工作人员并不关心信件的整体编号大小，而是按照邮政编码从右到左逐位分拣。这正是基数排序的精髓所在。

算法的核心在于"分桶-收集"机制。对于十进制数，我们准备10个桶（0-9），然后：

1. 第一轮按个位数分桶
2. 第二轮按十位数分桶
3. 依此类推直到最高位

关键点：每一轮分桶后必须保持前一轮的相对顺序，这就是为什么基数排序必须是稳定排序的原因。

1.2 LSD vs MSD实现对比

1.2.1 LSD（最低位优先）实现

LSD就像搭积木，必须从最底层开始：

// 伪代码示例 void radix_sort_LSD(int arr[], int n) { int max_val = find_max(arr, n); for (int exp = 1; max_val/exp > 0; exp *= 10) { counting_sort_by_digit(arr, n, exp); } }

实际工程中，我们通常用字节(byte)而非十进制位来处理，因为计算机处理字节更高效。32位整数可分为4个字节（每次处理8位），这样只需要4轮排序。

1.2.2 MSD（最高位优先）实现

MSD更像是快速排序的分治策略：

// 伪代码示例 void radix_sort_MSD(int arr[], int low, int high, int digit) { if (high <= low || digit < 0) return; // 分桶 vector<vector<int>> buckets(10); for (int i = low; i <= high; i++) { int d = get_digit(arr[i], digit); buckets[d].push_back(arr[i]); } // 递归处理每个桶 int index = low; for (auto &bucket : buckets) { int bucket_size = bucket.size(); for (int j = 0; j < bucket_size; j++) { arr[index++] = bucket[j]; } radix_sort_MSD(arr, index - bucket_size, index - 1, digit - 1); } }

1.3 时间复杂度与工程优化

理论时间复杂度为O(d*(n+k))，其中：

• d是最大数字的位数
• n是元素个数
• k是基数（十进制为10）

但在实际工程实现中，我们可以获得接近O(n)的性能：

1. 字节分块处理：将32位整数分为4个字节，每轮处理8位（k=256）
2. 计数排序优化：使用前缀和技巧避免物理分桶
3. 指针交换：通过交换指针而非数据移动减少内存操作

// 优化后的计数排序部分 void counting_sort_by_byte(int arr[], int n, int byte_pos) { int count[256] = {0}; int *output = malloc(n * sizeof(int)); // 统计频率 for (int i = 0; i < n; i++) { int byte = (arr[i] >> (byte_pos * 8)) & 0xFF; count[byte]++; } // 计算前缀和 for (int i = 1; i < 256; i++) { count[i] += count[i-1]; } // 逆序填充保持稳定性 for (int i = n-1; i >= 0; i--) { int byte = (arr[i] >> (byte_pos * 8)) & 0xFF; output[--count[byte]] = arr[i]; } // 指针交换避免数据拷贝 memcpy(arr, output, n * sizeof(int)); free(output); }

2. 力扣128题实战应用

2.1 问题重述与分析

题目要求找出未排序整数数组中最长连续序列的长度。例如： 输入：[100,4,200,1,3,2] 输出：4（因为最长连续序列是[1,2,3,4]）

传统解法有两种：

1. 哈希表法：O(n)时间复杂度，O(n)空间复杂度
2. 排序法：O(nlogn)时间复杂度

但哈希表在C语言中实现复杂，而排序法的时间复杂度不够理想。基数排序提供了第三种选择。

2.2 基数排序的特殊处理

2.2.1 负数处理技巧

计算机中负数用补码表示，直接排序会导致负数排在正数之后。解决方案：

// 符号位翻转 for (int i = 0; i < numsSize; i++) { nums[i] ^= 0x80000000; // 翻转最高位 } // 排序完成后恢复 for (int i = 0; i < numsSize; i++) { nums[i] ^= 0x80000000; }

2.2.2 去重优化

在基数排序过程中可以顺便去重：

// 在收集阶段检查重复 int last = output[0]; int new_size = 1; for (int i = 1; i < n; i++) { if (output[i] != last) { output[new_size++] = output[i]; last = output[i]; } }

2.3 完整解决方案

int longestConsecutive(int* nums, int numsSize) { if (numsSize == 0) return 0; // 基数排序实现（略，见前文） radix_sort(nums, numsSize); // 查找最长序列 int max_len = 1, current_len = 1; for (int i = 1; i < numsSize; i++) { if (nums[i] == nums[i-1]) continue; // 跳过重复 if (nums[i] == nums[i-1]+1) { current_len++; max_len = current_len > max_len ? current_len : max_len; } else { current_len = 1; } } return max_len; }

3. 性能对比与实测数据

3.1 理论分析

3.2 实测数据

在LeetCode测试用例上的表现（C语言实现）：

注意：基数排序在数据量极大时优势明显，但需要确保数据是整数类型。

4. 工程实践中的技巧与陷阱

4.1 内存优化技巧

1. 原地排序变体：可以通过巧妙的位操作实现部分原地排序，但会牺牲稳定性
2. 缓冲区复用：预先分配好临时缓冲区，避免频繁内存分配
3. 位压缩：对于小范围整数，可以用更小的数据类型存储中间结果

4.2 常见错误

1. 稳定性破坏：

// 错误示例：正序填充会破坏稳定性 for (int i = 0; i < n; i++) { output[count[byte]++] = arr[i]; // 错误！ }

2. 符号位处理遗漏：

// 忘记处理负数会导致排序错误 // 必须进行符号位翻转

3. 字节顺序混淆：

// 大端小端系统处理不当会导致错误 // 建议统一使用小端处理 int byte = (num >> (byte_pos * 8)) & 0xFF; // 正确

4.3 扩展应用

1. 字符串排序：将字符串看作256进制的数，使用MSD基数排序
2. 多关键字排序：如先按日期排序，同日期再按ID排序
3. 并行化实现：每轮分桶过程可以并行处理

基数排序的这种"分而治之"思想，可以推广到许多需要高效处理的领域。当处理海量数据时，它往往能带来意想不到的性能提升。