直方图排序（Histogram sort）的具体时间复杂度是多少？

首先明确：你提供的代码是数组直方图打印工具，不属于直方图排序的实现，二者逻辑和时间复杂度有明显区别。

核心时间复杂度结论 #

直方图排序是桶排序的特殊变体，属于分布排序的一种，三类时间复杂度如下：

• 最优时间复杂度：O(n + k)
• 平均时间复杂度：O(n + k)
• 最坏时间复杂度：O(n + k)

其中n为待排序元素的总数量，k为待排序元素的取值区间大小（即待排序数组中「最大值-最小值+1」）。

复杂度推导依据 #

直方图排序的执行逻辑分三步，每一步的时间开销对应如下：

1. 遍历待排序数组，找到最大值和最小值确定取值区间：时间开销O(n)
2. 二次遍历待排序数组，统计每个值出现的频次，构建直方图计数数组：时间开销O(n)
3. 遍历直方图计数数组，按照频次将对应数值依次回填到结果数组中完成排序：时间开销O(k)

总时间开销为三步之和，即O(n) + O(n) + O(k) = O(n + k)。当取值区间k远小于元素数量n时，直方图排序的时间效率接近线性O(n)，性能远高于常规的比较类排序算法；但如果待排序元素取值范围极大（比如元素为无界整数、浮点数），k的开销会显著上升，此时不适合使用该算法。

标准直方图排序实现示例 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void histogramSort(vector<int>& arr) {
    if (arr.empty()) return;
    // 第一步：确定取值区间
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    // 第二步：构建直方图计数
    vector<int> count(range, 0);
    for (int num : arr) {
        count[num - minVal]++;
    }
    // 第三步：回填数组完成排序
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + minVal;
            count[i]--;
        }
    }
}

int main() {
    vector<int> arr = {10, 9, 12, 4, 5, 2, 8, 5, 3, 1};
    histogramSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

你提供的直方图打印代码复杂度说明 #

你给出的打印直方图的代码时间复杂度为O(n * k)，其中n是数组长度，k是数组的最大值，因为外层循环遍历从0到最大值的所有整数（共k次），内层每次循环遍历整个数组（共n次），和排序逻辑的时间复杂度有明显差异。

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