在C中使用GCC编译器执行快速排序时出现分段错误

Question

我编写了以下C99代码来对固定数组执行快速排序。然而，在打印初始数组之后，它给出了一个分段错误。我现在没有任何调试器，我使用KWrite，然后使用终端来编译和运行。代码如下:

#include <stdio.h>
#define LEN 8
int arr[8] = {3,5,7,1,2,4,6,8};
void printarr()
{
    printf("n");
    for (int i = 0; i<LEN; i++)
        printf("t %d", arr[i]);
    printf("n");
}

void quicksort(int _left,int _right)
{
    int left = _left;
    int right = _right;
    int pivot = (left+right)/2;
    while (left<=right)
    {
        while(pivot>arr[left])
            left--;
        while (pivot<arr[right])
            right++;
        if(left<=right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = arr[temp];
            left++;
            right--;
        }
    }
    if (_left<right)
        quicksort(_left, right);
    else
        quicksort(left, _right);
}
int main()
{
    int left = 0, right = LEN-1;
    printf("Unsorted array:");
    printarr();
    quicksort(left,right);
    printf("Sorted array:");
    printarr();
}

请查看一下，让我知道是哪部分代码导致了这个问题

Answer 1

至少

int temp = arr[right];
arr[right] = arr[left];
arr[left] = arr[temp];

将不做你认为它会做的事。

将值(不是索引)存储在第一行的temp中，然后在第三行中将其用作索引。那可不会有好结果的。

相反，您希望使用该值作为值:

int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;

在比较pivot(一个索引)和arr[right]/arr[left](一个值)时，您也有类似的问题。

设置left和right的循环也会引起悲伤。您应该递增 left，因为您希望将其发送到数组的末尾，而递减 right，出于类似的原因。

Answer 2

在您的代码中，left = 0在quicksort函数中。,

while(pivot>arr[left])
        left--;

这里

，在此代码中，如果pivot的值大于arr[left]，即arr[0]，则left将变为负值。这很可能导致你的代码出现seg fault .

我想根据你的代码，正确的版本应该是

while(pivot>arr[left])      //elements < pivot on the left side
    left++;
while (pivot<arr[right])   //elemenst > pivot in the right side
    right--;

注意

也要明白，在你的递归调用中，我找不到任何终止条件。

您希望在满足特定条件时结束递归。在本例中，当_left >= _right。这应该在开始时检查，以确保您的函数没有进入无限递归。