是否存在计数排序（Count Sort）的更优实现方案？

你这段代码确实实现了支持负数的计数排序，但在内存效率、代码简洁性和执行效率上还有不少优化空间，下面是具体的优化方向和实现：

原代码的主要可优化点 #

• 没必要修改原输入数组：原代码直接把数组元素减去min偏移，会破坏原始数据，完全可以在统计计数时动态计算偏移
• 计数结构冗余：用std::pair<int, int>存原始值和计数纯属浪费，计数数组的索引加上min就是原始值，只需要存计数即可
• 最值查找效率低：两次遍历数组找min和max，改成一次遍历就能同时拿到两个值，减少一次O(n)的开销
• 结果生成不够高效：循环多次push_back可以改成提前分配内存，直接批量填充

优化后的代码实现 #

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {12,31,300,13,21,3,46,54,44,44,9,-1,0,-1,-1};
    
    // 空数组直接返回
    if (arr.empty()) {
        return 0;
    }

    // 一次遍历同时获取min和max
    int min_val = arr[0];
    int max_val = arr[0];
    for (int num : arr) {
        if (num < min_val) min_val = num;
        if (num > max_val) max_val = num;
    }

    // 计数数组：大小为(max_val - min_val + 1)，只存出现次数
    int count_size = max_val - min_val + 1;
    std::vector<int> count(count_size, 0);
    for (int num : arr) {
        // 计算当前元素在计数数组中的索引，不用修改原数组
        int idx = num - min_val;
        count[idx]++;
    }

    // 生成排序后的数组：提前分配内存，避免多次push_back
    std::vector<int> sorted_arr;
    sorted_arr.reserve(arr.size());
    for (int i = 0; i < count_size; ++i) {
        // 原始值 = 索引 + min_val
        int original_num = i + min_val;
        // 批量填充对应次数的元素
        sorted_arr.insert(sorted_arr.end(), count[i], original_num);
    }

    // 输出结果
    for (int num : sorted_arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

优化后的优势 #

1. 内存更高效：去掉了冗余的pair结构，计数数组只存整数计数，内存占用减少近一半
2. 不破坏原始数据：全程没有修改输入数组的元素
3. 执行效率更高：减少了一次数组遍历，结果生成用insert批量填充比循环push_back更高效
4. 代码更简洁：逻辑清晰，去掉了不必要的复杂操作

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