C语言快速排序处理大数组时出现Segmentation Fault求助

问题描述 #

实现的C语言快速排序在处理元素数少于30000的数组时运行正常，但处理更大数组时，在swap(&vet[sup], &vet[(sup-inf+1)/2]);行触发Segmentation Fault，不确定是栈溢出还是指针问题导致。

出错代码 #

void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
} 
int partition(int inf, int sup, int vet[]){
    while (inf<sup){
        while (vet[inf]<=vet[sup] && inf<sup){inf++;}
        while (vet[inf]<=vet[sup] && inf<sup){sup--;}
        if (inf<sup){swap(&vet[inf], &vet[sup]);}
    }
    return inf;
}
void median (int inf, int sup, int vet[]){ //select the median of the first, last and midle value of the vector
    if (vet[inf]>vet[(sup-inf+1)/2])
        swap(&vet[inf], &vet[(sup-inf+1/2)]);
    if (vet[sup]>vet[(sup-inf+1)/2])
        swap(&vet[sup], &vet[(sup-inf+1)/2]);  
    else if (vet[sup]<vet[inf])
        swap(&vet[sup], &vet[inf]);    
}
void quicksort(int inf, int sup, int vet[]){
    if (inf<sup){
        median(inf, sup, vet);    
        int piv=partition(inf, sup, vet);
        quicksort(inf, piv-1, vet);
        quicksort(piv+1, sup, vet);
    }
}

错误分析与修复 #

1. 中位数索引计算错误（直接触发越界） #

median函数的中间元素索引逻辑完全错误：

• 当前用(sup-inf+1)/2计算的是子数组长度的一半，而非数组的实际索引。正确的中间索引应为inf + (sup - inf) / 2（避免整数溢出的安全写法），需要加上子数组的起始位置inf才能定位到正确元素。
• 代码存在笔误：swap(&vet[inf], &vet[(sup-inf+1/2)]);中1/2是整数除法，结果为0，导致索引计算彻底失效。

修复后的median函数：

void median(int inf, int sup, int vet[]) {
    int mid = inf + (sup - inf) / 2; // 正确定位子数组的中间元素
    // 将中位数交换到sup位置，作为partition的基准
    if (vet[inf] > vet[mid])
        swap(&vet[inf], &vet[mid]);
    if (vet[sup] > vet[mid])
        swap(&vet[sup], &vet[mid]);
    if (vet[sup] < vet[inf])
        swap(&vet[sup], &vet[inf]);
}

2. 递归深度过大导致栈溢出（大数组场景） #

快速排序最坏情况下递归深度为O(n)，当数组元素数量过大时，递归调用栈会超出系统默认栈容量（通常为几MB），触发栈溢出。

解决方法：采用尾递归优化，优先递归处理较小的子数组，较大的子数组用循环代替递归，大幅降低递归深度：

void quicksort(int inf, int sup, int vet[]) {
    while (inf < sup) {
        median(inf, sup, vet);
        int piv = partition(inf, sup, vet);
        // 递归处理更小的子数组，减少栈占用
        if (piv - inf < sup - piv) {
            quicksort(inf, piv - 1, vet);
            inf = piv + 1;
        } else {
            quicksort(piv + 1, sup, vet);
            sup = piv - 1;
        }
    }
}

3. Partition函数逻辑错误 #

原partition的双向扫描条件错误，两个循环均使用vet[inf]<=vet[sup]，会导致无法正确划分元素，甚至出现死循环。修复为标准的单边扫描实现：

int partition(int inf, int sup, int vet[]) {
    int pivot = vet[sup]; // 取中位数所在的sup位置为基准
    int i = inf - 1; // 记录小于等于基准的元素的最后位置
    for (int j = inf; j < sup; j++) {
        if (vet[j] <= pivot) {
            i++;
            swap(&vet[i], &vet[j]);
        }
    }
    swap(&vet[i + 1], &vet[sup]); // 将基准放到正确的划分位置
    return i + 1;
}

最终修复后的完整代码 #

#include <stdio.h>

void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
} 

int partition(int inf, int sup, int vet[]) {
    int pivot = vet[sup];
    int i = inf - 1;
    for (int j = inf; j < sup; j++) {
        if (vet[j] <= pivot) {
            i++;
            swap(&vet[i], &vet[j]);
        }
    }
    swap(&vet[i + 1], &vet[sup]);
    return i + 1;
}

void median(int inf, int sup, int vet[]) {
    int mid = inf + (sup - inf) / 2;
    if (vet[inf] > vet[mid])
        swap(&vet[inf], &vet[mid]);
    if (vet[sup] > vet[mid])
        swap(&vet[sup], &vet[mid]);
    if (vet[sup] < vet[inf])
        swap(&vet[sup], &vet[inf]);
}

void quicksort(int inf, int sup, int vet[]) {
    while (inf < sup) {
        median(inf, sup, vet);
        int piv = partition(inf, sup, vet);
        if (piv - inf < sup - piv) {
            quicksort(inf, piv - 1, vet);
            inf = piv + 1;
        } else {
            quicksort(piv + 1, sup, vet);
            sup = piv - 1;
        }
    }
}

// 测试用例
int main() {
    int arr[100000];
    for (int i = 0; i < 100000; i++) {
        arr[i] = 100000 - i;
    }
    quicksort(0, 99999, arr);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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