简单快速排序程序中的分段错误

Question

当我尝试执行以下代码时，它导致了分段错误。使用在线 GDB，程序会在第一次调用分区函数后停止工作。该程序从不进行递归，并在调用 partition() 后立即停止工作。

#include <stdio.h>

int partition(int arr[], int len)
{
    int pivot = len / 2;
    int left = 0;
    int right = len - 1;
    int temp;

    while (right != 0 || left !=0)
    {
        if (right != pivot)
        {
            if (arr[right] < arr[pivot])
            {
                temp = arr[right];
                arr[right] = arr[pivot];
                arr[pivot] = temp;
                pivot = right;
            }
            else right--;
        }
        
        else
        {
            if (arr[left] > arr[pivot])
            {
                temp = arr[left];
                arr[left] = arr[pivot];
                arr[pivot] = temp;
                pivot = left;
            }
            else left++;
        }


    }

    return pivot;
}


void quicksort(int arr[], int len)
{
    if (len > 1)
    {
        int pivot = partition(arr, len);
        quicksort(arr, pivot);
        quicksort(arr+pivot+1, len-pivot-1);
    }
}


int main()
{
    int arr[] = {1,6,3,2,9,5,4,7,8};
    quicksort(arr, 9);

    for (int i =0; i< 9; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

由于某些原因调用分区函数时，变量 pivot、left、right 都用垃圾值初始化。

请帮忙。

Answer 1

您的主要 while 条件 (right != 0 || left !=0) 存在缺陷。它所需要的只是一个 lower-bound 通过 else left++' 碰撞并且该条件将是 perma-true，最终导致段破坏。

相反，你想左右崩溃，直到他们达成共识。例如：while (right > left)

简单快速排序程序中的分段错误

Segementation fault in a simple Quicksort program

c

quicksort

segmentation-fault