递归冒泡排序大数组触发栈溢出（错误码0xC00000FD）求助

问题描述 #

使用递归实现的冒泡排序处理40000条数据时程序冻结，报错Process returned -1073741571 (0xC00000FD)，已知为栈溢出错误，但未定位到具体原因。需求是支持排序1000万条乱序数据（数据取自预先创建的文本文件），相关C语言代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void bubbleSort(int *arr, int n){
    int i, temp;
    for(i = 0; i < n-1; i++){
        if(arr[i] > arr[i+1]){
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
    if(n == 1){
        return;
    }
    else{
        bubbleSort(arr, n-1);
    }
}

int main(){

    double time_spent = 0.0;

    int n, i, num, *Aleatorio, cont = 0;

    FILE *f = fopen("archivo.txt","rt");

    printf("Ingrese la cantidad de datos a analizar: ");
    scanf("%d", &n);

    Aleatorio = (int*)malloc(n*sizeof(int));

    if(Aleatorio == NULL){
        printf("AAAAAAAAAAAAAAAAAAAA");
    }
    else{
        for(i = 0; i < n; i++){
            fscanf(f, "%d", &num);
            Aleatorio[i] = num;
        }
    }
    fclose(f);

    /*
    printf("\n\nArray Desordenado : \n");
    for(i = 0; i < n; i++){
        printf("%d ",Aleatorio[i]);
        //cont++;
    }
    */
    clock_t begin = clock();

    bubbleSort(Aleatorio, n);

    clock_t end = clock();
    free(Aleatorio);

    printf("\n\n\n\n\n\n\nArray Ordenado : \n");
    for(i = 0; i < n; i++){
        printf("%d ",Aleatorio[i]);
        cont++;
    }

    time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
    printf("\n\n cont = %d", cont);
    printf("\n\nThe elapsed time is %f seconds", time_spent);
    return 0;
}

栈溢出原因分析 #

递归版冒泡排序的调用深度等于数组长度n。例如处理40000条数据时，递归调用会嵌套40000层，而程序默认栈空间通常仅几MB（Windows下多为1-8MB），每一层递归都会在栈上保存返回地址、参数、局部变量，40000层的调用会直接耗尽栈空间，触发栈溢出错误。

另外，冒泡排序本身时间复杂度为O(n²)，即便解决栈溢出问题，处理1000万条数据的时间成本也完全不可接受，递归版本还额外增加了栈开销，完全不适合大数据量排序场景。

解决方案 #

1. 改用迭代版冒泡排序（解决栈溢出，但仍不适合千万级数据） #

将递归逻辑改为循环，彻底避免栈溢出：

void bubbleSort(int *arr, int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        // 每一轮将最大元素"冒"到当前未排序区间末尾
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

注意：迭代版冒泡排序时间复杂度仍为O(n²)，处理1000万条数据会花费极长时间，实际不可用。

2. 改用高效排序算法（满足千万级数据需求） #

针对1000万条数据，必须使用时间复杂度O(n log n)的排序算法，比如快速排序、归并排序，或直接使用标准库的qsort函数（底层多为高度优化的混合排序实现）：

使用标准库qsort示例：

// qsort要求的比较函数
int compareInt(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

// 在main函数中替换原bubbleSort调用：
qsort(Aleatorio, n, sizeof(int), compareInt);

qsort是C标准库提供的高效排序函数，经过工业级优化，能轻松处理千万级数据，同时避免栈溢出问题（底层实现多为迭代或递归深度可控的版本）。

3. 其他关键优化点 #

• 内存检查增强：原代码中malloc失败仅打印字符串，应直接终止程序，避免后续非法访问空指针。
• 避免访问已释放内存：原代码在free(Aleatorio)后打印数组，属于未定义行为，会导致崩溃或乱码，必须将打印逻辑移到free之前。
• 大文件读取优化：读取1000万条数据时，fscanf效率较低，可改用fread批量读取或内存映射文件，提升读取速度。

修正后的main函数关键部分：

// ... 读取数据完成后 ...
clock_t begin = clock();

qsort(Aleatorio, n, sizeof(int), compareInt);

clock_t end = clock();

// 先打印数组，再释放内存
printf("\n\nArray Ordenado : \n");
for(i = 0; i < n; i++){
    printf("%d ",Aleatorio[i]);
    cont++;
}

free(Aleatorio);

time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
printf("\n\n cont = %d", cont);
printf("\n\nThe elapsed time is %f seconds", time_spent);

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