排序问题中如何兼顾时间与内存限制？解决OOM错误

问题说明 #

需对自然数进行升序排序，运行时触发OutOfMemory（OOM）错误，需满足以下约束：

• 内存上限：8MB
• 运行时间上限：5秒
• 输入规则：第一行输入数字个数N（1 ≤ N ≤ 10,000,000），后续N行每行输入一个≤10,000的自然数

现有代码问题分析 #

尝试的两段冒泡排序代码均存在核心问题：

1. 内存超限：
   • 第一段代码分配N个int数组，当N=10^7时，内存占用为10^7 * 4字节 = 40MB，远超8MB限制；
   • 第二段代码误用long*却按sizeof(int)分配内存，实际存储会越界，且long类型本身占8字节，若正确分配内存会占用80MB，同样超限。
2. 时间超限：冒泡排序时间复杂度为O(n²)，10^7规模的数据需要约1e14次操作，完全无法在5秒内完成。

优化方案：计数排序 #

由于输入数据的取值范围固定为1~10000，采用计数排序（桶排序的变种）是最优选择：

• 仅需一个大小为10001的数组，统计每个数字出现的次数；
• 内存占用仅约39KB（10001*4字节），远低于8MB限制；
• 时间复杂度为O(N + K)（N为数据量，K为取值范围大小），10^7规模的数据可在5秒内处理完成。

优化后代码 #

#include <stdio.h>
#include <string.h>

int main() {
    int N;
    scanf("%d", &N);
    
    // 数组索引对应数字，值对应出现次数，覆盖1~10000的所有可能
    int count[10001] = {0};
    
    // 统计每个数字出现次数
    for (int i = 0; i < N; ++i) {
        int num;
        scanf("%d", &num);
        count[num]++;
    }
    
    // 按升序输出结果
    for (int i = 1; i <= 10000; ++i) {
        for (int j = 0; j < count[i]; ++j) {
            printf("%d\n", i);
        }
    }
    
    return 0;
}

方案验证 #

• 内存合规：计数数组仅占用40004字节，约39KB，远低于8MB上限；
• 时间合规：读取数据和输出数据均为线性操作，10^7次IO和计算在C语言环境下可轻松在5秒内完成。

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