编写Quick Sort程序运行时触发Segmentation Fault问题求助

你的快速排序程序触发Segmentation Fault的核心原因是递归缺少终止条件，导致无限递归调用耗尽栈空间。

在quick_sort函数中，当left >= right时，当前子数组要么没有元素，要么只有一个元素，完全不需要继续排序，但你的代码会持续发起递归调用，最终引发栈溢出。

修复后的代码 #

#include <iostream>

using namespace std;

int partition(int arr[],int left,int right,int pivot) {

    while(left <= right) {
        while(arr[left] < pivot) {
            left++;
        }
        while(arr[right] > pivot) {
            right--;
        }
        if(left <= right) {
            swap(arr[left],arr[right]);
            left++;
            right--;
        }
    }
    return left;
}

void quick_sort(int arr[],int left,int right) {
    // 添加递归终止条件：子数组无需排序时直接返回
    if (left >= right) {
        return;
    }
    int pivot = arr[(left+right)/2];
    int index = partition(arr,left,right,pivot);
    quick_sort(arr,left,index-1);
    quick_sort(arr,index,right);
}

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int size = sizeof(arr)/sizeof(arr[0]);
    quick_sort(arr,0,size-1);
    for(int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

关键修改说明 #

• 在quick_sort函数开头加入if (left >= right) return;判断，当子数组的左边界大于等于右边界时，直接终止当前递归分支，避免无效的递归调用。

修改后程序可正常运行，输出结果为：1 2 3 4 5 6 7 8 9 10

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