基数排序：打破比较下界的正确姿势
原文中文，约22900字，阅读约需55分钟。
📝
内容提要
基数排序（Radix Sort）的时间复杂度可达 O(nk)，超越了比较排序的 O(n log n) 下界。其核心在于直接读取元素的位，而非进行比较。基数排序适合固定长度的整数和字符串，但在处理大元素和变长字符串时效果较差。选择排序算法时需考虑数据特征与实际性能。
🔎
延伸解读
基数排序的适用场景
基数排序在处理固定长度的整数和字符串时表现优异，尤其适合大规模数据集。对于32位和64位整数，使用基数256的LSD基数排序可以在4轮内完成排序，效率高于比较排序。然而，当数据元素较大或长度不固定时，基数排序的性能可能下降，因此在选择排序算法时需考虑数据特征。
缓存友好性与性能
基数排序的内存访问模式可能导致缓存未命中，影响性能。尤其在处理大数据时，散射写入的随机性会导致缓存效率低下。为了优化性能，可以考虑使用ska_sort等缓存友好的实现，或在小数组时切换到插入排序，以提高缓存利用率。
基数选择的重要性
基数的选择直接影响基数排序的轮数和内存使用。选择合适的基数可以在保证性能的同时，避免过大的计数数组导致的缓存抖动。通常，基数256是一个安全的选择，适合大多数场景，但在特定情况下，可能需要根据数据规模调整基数以优化性能。
❓
Q&A
基数排序的时间复杂度是多少？
基数排序的时间复杂度为 O(nk)，其中 k 是键的位数。
基数排序是如何打破比较排序的下界的？
基数排序通过直接读取元素的位进行排序，而不是通过比较，因此不违反比较排序的 O(n log n) 下界。
基数排序适合处理哪些类型的数据？
基数排序适合固定长度的整数和字符串，但在处理大元素和变长字符串时效果较差。
基数排序的主要变体有哪些？
基数排序的主要变体有 LSD（最低有效位）和 MSD（最高有效位），它们在处理方向和稳定性上有所不同。
选择基数排序时需要考虑哪些因素？
选择基数排序时需考虑键的长度、数据规模、元素大小和稳定性需求。
为什么数据库排序通常不使用基数排序？
数据库排序通常不使用基数排序，因为变长键和复杂比较语义的问题使得基数排序不适用。
🏷️
