C语言中使用quicksort处理动态二维数组出现段错误问题排查

需求是实现类似JavaScript中arr.sort((a,b) => a[0] - b[0])的功能——根据二维数组的第一列值对行进行排序。静态二维数组arr使用qsort和自定义比较函数可正常排序，但动态分配的int** rect数组排序时出现段错误。

错误原因分析 #

1. 内存分配循环条件错误 #

代码中分配rect的行指针时，循环条件误用了COLS作为上限，实际需要分配ROWS个行指针：

// 错误：循环上限应为ROWS，而非COLS
for(int i = 0; i < COLS; i++){
    *(rect+i) = malloc(COLS*sizeof(int));
}

这会导致rect数组中仅前COLS个指针指向有效内存，剩余ROWS - COLS个指针是未初始化的野指针，后续访问或排序时直接触发段错误。

2. qsort的元素大小参数错误 #

qsort的第三个参数是待排序数组中单个元素的字节大小：

• 静态二维数组arr是连续内存块，每个"元素"是一整行的连续整数，因此元素大小为COLS*sizeof(int)，这部分逻辑正确。
• 动态int** rect是指针数组，数组中的每个元素是int*类型的指针（指向独立的行内存），因此单个元素的大小应为sizeof(int*)。原代码传入错误的元素大小，会导致qsort越界读写内存，触发段错误。

3. 比较函数的类型转换错误 #

对于int** rect，qsort传入比较函数的a和b是指向数组元素的指针（即int**类型），原比较函数直接转换为int*会导致指针类型不匹配，访问错误的内存地址。

int** rect与静态二维数组arr的核心差异 #

• 存储结构不同：
  • 静态二维数组arr：是一块连续的线性内存，行与行紧密排列，arr[0]之后直接是arr[1]的内存，无间隔。qsort可直接将每一行当作连续元素块处理。
  • 动态int** rect：是"指针数组+分散行内存"的结构，rect本身是数组，每个元素指向独立分配的行内存，这些行的内存地址不一定连续。qsort排序的是rect数组里的指针，而非行内存本身。
• qsort处理逻辑不同：
  • 静态数组：排序时交换整行的内存数据（COLS*sizeof(int)字节）。
  • 动态指针数组：排序时仅交换指针值（sizeof(int*)字节），行内存本身的位置不变，仅指针顺序被调整。

修正后的代码示例 #

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

// 适配int**类型的比较函数
int comp(const void *a, const void *b){
    const int* rowA = *(const int**)a;
    const int* rowB = *(const int**)b;
    return rowA[0] - rowB[0];
}

int main(){
    int arr[][4] = {
       {3,2,5,3}, {1,0,5,2},{0,2,2,4},{0,4,4,5}
    };
    int ROWS = sizeof(arr)/sizeof(arr[0]);
    int COLS = sizeof(arr[0])/sizeof(arr[0][0]);

    int **rect = malloc(ROWS*sizeof(int*));
    // 修正循环上限为ROWS
    for(int i = 0; i < ROWS; i++){
        rect[i] = malloc(COLS*sizeof(int));
    }
    // 复制数据
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            rect[i][j] = arr[i][j];
        }
    }

    // 修正元素大小为sizeof(int*)
    qsort(rect, ROWS, sizeof(int*), comp);

    // 打印结果并释放内存
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            printf("%d ", rect[i][j]);
        }
        printf("\n");
        free(rect[i]);
    }
    free(rect);
    return 0;
}

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