调试C语言中三维数组列排序的QuickSort变体程序

问题背景 #

要对尺寸为P×M×N的三维数组，按每个切片（currP对应的二维层）的列元素和进行排序，基于快速排序实现了QuickSort_3D函数，调用时通过循环遍历每个切片：

for (int p = 0; p < P; p++)
{
    QuickSort_3D(0, N, p);
}

但程序执行几次调用后，在free(Sum);处崩溃，报错Process returned -1073740940 (0xC0000374)（堆损坏错误）。

错误分析 #

从代码中可定位出几个导致堆损坏的关键问题：

1. Sum数组越界访问

   • malloc((R - L) * sizeof(int))仅分配了对应L到R-1列的和的存储空间（共R-L个元素，索引范围0到R-L-1）。
   • 但填充Sum的循环是for (int i = 0; i < R; i++)，遍历了0到R-1的所有列，当L>0时，i-L会出现负数（比如L=2、i=0时，i-L=-2），直接越界访问Sum的内存区域，破坏堆结构，最终导致free时崩溃。
   • 同时，循环里Sum[i] += Arr3D[currP][j][i];是错误的，应该用Sum[i-L]累加对应列的和，否则同样会越界。

2. 基准值索引计算错误

   • 原代码B = Sum[(R - (R-L)/2) - L];的逻辑混乱，会导致访问Sum数组的非法索引，进一步破坏堆。正确的中间索引应为当前区间对应的Sum偏移：(R-L)/2。

3. 变量重定义冲突

   • 函数开头已定义int i, j;，后面的循环又定义int i = 0;，会导致变量作用域冲突，混淆逻辑，甚至引发未定义行为。

4. 边界索引错误

   • 原代码中j = R的初始值错误，因为列索引范围是0到N-1，初始调用的R=N，直接用j=R会访问超出列范围的索引。

修复方案 #

针对上述问题逐一修正：

• 修正Sum数组填充逻辑：仅遍历当前排序区间[L, R-1]的列，循环变量改用col避免和函数内的i冲突；用Sum[col-L]正确累加对应列的和。
• 修正基准值选取：直接取当前Sum数组的中间元素作为基准。
• 移除变量重定义，确保变量作用域清晰。
• 修正边界索引：将j的初始值改为R-1，递归调用时保持右边界为开区间逻辑。

修正后的代码 #

void QuickSort_3D(int L, int R, int currP)
{
    printf("%d %d %d\n", L, R, currP);
    int B, tmp, i, j;
    // 只分配当前区间需要的内存
    int *Sum = (int *)malloc((R - L) * sizeof(int)); 
    // 遍历当前区间的列：L到R-1
    for (int col = L; col < R; col++)
    {
        Sum[col - L] = 0;
        for (int j = 0; j < M; j++)
        {
            Sum[col - L] += Arr3D[currP][j][col];
        }
    }
    // 取当前区间的中间元素作为基准
    B = Sum[(R - L)/2];
    printf("B = %d %d\n", B, (R-L)/2);
    i = L;
    j = R - 1; // 修正j的初始值，匹配列索引范围
    while (i <= j)
    {
        while (Sum[i - L] < B)
            i++;
        while (Sum[j - L] > B)
            j--;
        if (i <= j)
        {
            // 交换两列的所有元素
            for (int k = 0; k < M; k++)
            { 
                tmp = Arr3D[currP][k][i];
                Arr3D[currP][k][i] = Arr3D[currP][k][j];
                Arr3D[currP][k][j] = tmp;
            }
            // 交换Sum数组中对应的值
            tmp = Sum[i - L];
            Sum[i - L] = Sum[j - L];
            Sum[j - L] = tmp;
            i++;
            j--;
        }
    }
    printf("FREE\n");
    free(Sum);
    printf("%d %d\n", i, j);
    if (L < j)
    {
        QuickSort_3D(L, j + 1, currP); // 右边界改为j+1，保持开区间逻辑
    }
    if (i < R)
    {
        QuickSort_3D(i, R, currP);
    }
    printf("back\n");
}

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