实现Hoare快速排序时出现Segmentation Fault问题排查

先从这几个核心方向查问题 #

1. Hoare分区的边界越界 #

Hoare快排的分区逻辑特别容易踩越界的坑，尤其是当比较器逻辑出问题时，左右指针可能直接跑到数组外面：

• 如果所有元素和基准值都相等，指针可能一直移动直到超出数组范围
• 分区循环的终止条件写错（比如把<写成<=，或者反过来）
• 递归调用时传错边界参数（比如直接把pivot位置传给下一层，而不是pivot-1/pivot+1）

2. 自定义比较器的逻辑bug #

你的排序规则是「任务数多优先→罚分少优先→登录名字典序靠前」，比较器的返回值必须严格对应快排要求（正数/负数/0表示元素相对顺序），常见坑：

• 字符串比较用==代替strcmp，这比的是指针地址不是内容，直接搞乱排序逻辑
• 比较器返回值搞反（比如应该返回b->completed - a->completed却写成a->completed - b->completed，导致排序逻辑反向，干扰指针移动）
• 没处理空指针：如果name字段有NULL，调用strcmp直接崩

3. 递归终止条件写错 #

快排递归必须在low >= high时停下，如果写成low > high，会导致递归深度异常或者继续访问越界的数组位置

针对性代码检查步骤 #

假设你的代码结构类似下面的示例，重点盯这些点：

typedef struct {
    int completed;
    int penalty;
    char* name;
} Participants;

// 自定义比较器：返回<0表示a该排在b前面，>0表示a该排在b后面
int compare(const Participants* a, const Participants* b) {
    if (a->completed != b->completed) {
        return b->completed - a->completed; // 任务数多的靠前，所以用b减a
    }
    if (a->penalty != b->penalty) {
        return a->penalty - b->penalty; // 罚分少的靠前，a罚分小就返回负数
    }
    return strcmp(a->name, b->name); // 字典序小的靠前，strcmp返回值刚好符合
}

void swap(Participants* x, Participants* y) {
    Participants temp = *x;
    *x = *y;
    *y = temp;
}

int hoare_partition(Participants arr[], int low, int high) {
    Participants pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    while (1) {
        // 找左边第一个不该在基准前面的元素
        do {
            i++;
        } while (compare(&arr[i], &pivot) < 0);
        // 找右边第一个不该在基准后面的元素
        do {
            j--;
        } while (compare(&arr[j], &pivot) > 0);
        if (i >= j) {
            return j;
        }
        swap(&arr[i], &arr[j]);
    }
}

void quick_sort(Participants arr[], int low, int high) {
    if (low < high) { // 终止条件：low >= high时停止递归
        int pi = hoare_partition(arr, low, high);
        quick_sort(arr, low, pi);
        quick_sort(arr, pi + 1, high);
    }
}

必查细节： #

• 分区里的do-while循环条件是否和比较器返回值匹配？要是比较器返回值搞反，循环会一直跑直到数组越界，直接崩
• 字符串比较时，name字段是不是肯定不为空？要是有元素的name是NULL，strcmp直接触发段错误
• 递归参数：Hoare分区返回的j是左分区最后一个索引，所以左递归是low到pi，右递归是pi+1到high，写错直接出问题
• 所有元素完全相同时，分区逻辑能不能正常终止？比如i和j会不会相遇，而不是一直移动

测试用例调试建议 #

针对那13条触发崩溃的数据，这么排查：

1. 加日志打印每次递归的low和high，看边界是不是正常
2. 在比较器里加日志，打印每次比较的元素值和返回结果，有没有异常的比较（比如空指针）
3. 用gdb挂进程，看段错误发生时的调用栈，确认是在比较器里还是分区循环里出的错

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