基数排序：打破比较下界的正确姿势
💡
原文中文，约22900字，阅读约需55分钟。
📝
内容提要
基数排序（Radix Sort）的时间复杂度可达 O(nk)，超越了比较排序的 O(n log n) 下界。其核心在于直接读取元素的位，而非进行比较。基数排序适合固定长度的整数和字符串，但在处理大元素和变长字符串时效果较差。选择排序算法时需考虑数据特征与实际性能。
🎯
关键要点
- 基数排序的时间复杂度为 O(nk)，超越比较排序的 O(n log n) 下界。
- 基数排序通过直接读取元素的位来进行排序，而不是通过比较。
- 基数排序适合固定长度的整数和字符串，但在处理大元素和变长字符串时效果较差。
- 选择排序算法时需考虑数据特征与实际性能。
- 比较排序的下界证明基于决策树模型，假设排序算法只能通过两两比较获取信息。
- 基数排序不违反下界，因为它不依赖于比较，而是直接读取键的位。
- 基数排序的复杂度为 O(d * (n + radix))，其中 d 是位数，radix 是基数。
- 基数排序的有效性依赖于键的位数和基数的选择。
- 基数排序有两种主要变体：LSD（最低有效位）和 MSD（最高有效位），它们在处理方向和稳定性上有所不同。
- 计数排序是基数排序的基础，每一轮的排序本质上是一次计数排序。
- 基数的选择直接影响排序的轮数、内存使用和缓存行为。
- 基数排序的内存访问模式可能导致缓存未命中，影响性能。
- ska_sort 是一种缓存友好的基数排序实现，采用就地分区和自适应基数选择。
- 数据库排序通常不使用基数排序，主要因为变长键和复杂比较语义的问题。
- 基数排序在特定场景下表现优异，如大规模整数排序和固定长度字符串排序。
- 选择基数排序的判断框架包括键的长度、数据规模、元素大小和稳定性需求。
- 基数排序的历史悠久，但在通用场景中逐渐被比较排序算法取代。
❓
延伸问答
基数排序的时间复杂度是多少？
基数排序的时间复杂度为 O(nk)，其中 k 是键的位数。
基数排序是如何打破比较排序的下界的？
基数排序通过直接读取元素的位进行排序，而不是通过比较，因此不违反比较排序的 O(n log n) 下界。
基数排序适合处理哪些类型的数据？
基数排序适合固定长度的整数和字符串，但在处理大元素和变长字符串时效果较差。
基数排序的主要变体有哪些？
基数排序的主要变体有 LSD（最低有效位）和 MSD（最高有效位），它们在处理方向和稳定性上有所不同。
选择基数排序时需要考虑哪些因素？
选择基数排序时需考虑键的长度、数据规模、元素大小和稳定性需求。
为什么数据库排序通常不使用基数排序？
数据库排序通常不使用基数排序，因为变长键和复杂比较语义的问题使得基数排序不适用。
➡️
