基数排序：打破比较下界的正确姿势

基数排序的时间复杂度为 O(nk)，超越比较排序的 O(n log n) 下界。

基数排序通过直接读取元素的位来进行排序，而不是通过比较。

基数排序适合固定长度的整数和字符串，但在处理大元素和变长字符串时效果较差。

选择排序算法时需考虑数据特征与实际性能。

比较排序的下界证明基于决策树模型，假设排序算法只能通过两两比较获取信息。

基数排序不违反下界，因为它不依赖于比较，而是直接读取键的位。

基数排序的复杂度为 O(d * (n + radix))，其中 d 是位数，radix 是基数。

基数排序的有效性依赖于键的位数和基数的选择。

基数排序有两种主要变体：LSD（最低有效位）和 MSD（最高有效位），它们在处理方向和稳定性上有所不同。

计数排序是基数排序的基础，每一轮的排序本质上是一次计数排序。

基数的选择直接影响排序的轮数、内存使用和缓存行为。

基数排序的内存访问模式可能导致缓存未命中，影响性能。

ska_sort 是一种缓存友好的基数排序实现，采用就地分区和自适应基数选择。

数据库排序通常不使用基数排序，主要因为变长键和复杂比较语义的问题。

基数排序在特定场景下表现优异，如大规模整数排序和固定长度字符串排序。

选择基数排序的判断框架包括键的长度、数据规模、元素大小和稳定性需求。

基数排序的历史悠久，但在通用场景中逐渐被比较排序算法取代。