基数排序最优基数调整：2^log(n)的实现与原理疑问

一、为什么2^log(n)是接近最优的基数 #

基数排序的时间复杂度为 O(d(n + k))*，其中：

• d：排序轮数（即最大值以基数k为底的位数）
• n：数组元素个数
• k：基数大小

当基数取 k=2^floor(ln(n)) 时，代入复杂度公式可得：

• 轮数d = log_k(M) ≈ ln(M)/ln(n)（M为数组最大值）
• 时间复杂度简化为 O(n*ln(M)/ln(n))

这个选择能实现时间与空间的最优平衡：

• 若k过小（比如10进制），d会大幅增加，轮数变多导致总开销上升
• 若k过大（比如k>M），算法退化为计数排序，空间复杂度飙升至O(M)，对大M场景完全不适用
• 取接近n的2的幂时，d被压缩到极小范围（通常1-2轮），同时计数排序的空间开销O(k)控制在O(n)级别，在多数场景下内存可承受

二、对算法的核心影响 #

• 时间效率：轮数大幅减少，比如n=1024时，k=1024，若最大值≤1023，一轮即可完成排序；即使最大值是1024²，也仅需2轮，远少于10进制的轮数
• 空间开销：计数排序的count数组大小变为O(n)，属于可接受的内存范围
• 性能优化：因为基数是2的幂，可用位运算替代除法、取模操作（比如(arr[i] >> shift) & mask代替(arr[i]/exp)%k），硬件层面位运算比算术运算更快

三、基于你提供的代码的实现修改 #

需要修改三个核心部分：计算基数k、调整计数排序函数、修改基数排序主循环逻辑。

修改后的完整代码 #

#include <iostream>
#include <cmath>
using namespace std;

// 获取数组最大值
int getMax(int arr[], int n) {
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}

// 基于2^log(n)基数的计数排序，shift为当前处理的位偏移量，mask为基数对应的位掩码
void countSort(int arr[], int n, int shift, int mask) {
    int k = mask + 1; // 基数大小
    int* output = new int[n];
    int* count = new int[k](); // 初始化count数组为0

    // 统计每个"位段"的出现次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] >> shift) & mask;
        count[digit]++;
    }

    // 计算前缀和，确定每个元素在输出数组中的位置
    for (int i = 1; i < k; i++)
        count[i] += count[i - 1];

    // 从后往前构建输出数组，保证排序稳定性
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] >> shift) & mask;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // 将结果复制回原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];

    // 释放动态分配的内存
    delete[] output;
    delete[] count;
}

// 基数排序主函数，使用2^log(n)作为基数
void radixsort(int arr[], int n) {
    if (n <= 1) return;

    // 计算基数k=2^floor(ln(n))
    int log_n = floor(log(n));
    int k = 1 << log_n; // 等价于2^log_n
    int bits = log_n; // 每个"位段"的位数

    int max_val = getMax(arr, n);

    // 循环处理所有位段，直到最大值的所有位都被处理
    for (int shift = 0; (max_val >> shift) > 0; shift += bits) {
        int mask = k - 1; // 生成位掩码，比如k=8时mask=0b111
        countSort(arr, n, shift, mask);
    }
}

// 打印数组
void print(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

// 测试主函数
int main() {
    int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
    int n = sizeof(arr) / sizeof(arr[0]);

    radixsort(arr, n);
    print(arr, n);
    return 0;
}

关键修改点说明 #

1. 基数计算：
   通过floor(log(n))得到ln(n)的向下取整值，再用1 << log_n生成对应的2的幂次基数k，保证k是≤n的最大2的幂
2. 计数排序函数：
   • 用位偏移量shift和位掩码mask提取当前处理的"位段"，替代原代码中基于10进制的exp
   • 动态分配count和output数组，适配动态计算的基数k，避免固定数组大小的限制
3. 主循环逻辑：
   循环条件改为(max_val >> shift) > 0，每次循环将shift增加bits（即log_n），直到最大值的所有位都被处理完毕

四、注意事项 #

• 若题目中的log指以2为底的对数，可将log(n)替换为log2(n)，结果更准确
• 需处理n=1的边界情况，避免计算log(0)的错误
• 若使用C++11及以上标准，可用vector替代动态数组，避免手动管理内存的风险

内容的提问来源于stack exchange，提问作者CodingQuestions