Segfault在C中使用quicksort实现

Question

我在C中调试我的代码用于快速排序算法.它在运行时编译但失败并出现"分段错误".

任何人都可以帮我调试它并给我代码的工作版本吗？我知道互联网上现有的和有效的.但我真正想要的是找到我自己的代码的错误.

void myQuickSort(int list[],int head, int tail)
{
    int m = head;
    int n = tail;

    int key = list[m];
    ++head;
    while(head < tail)
    {
        while(list[head] < key)
        {
            ++head;
        }
        while(list[tail] >= key)
        {
            --tail;
        }
        //swamp two elements, to divide the array to two groups
        int temp = list[head];
        list[head] = list[tail];
        list[tail] = temp;

    }

    //get the pivot element in dividing position
    int temp = list[m];
    list[m] = list[head];
    list[head] = temp;

    myQuickSort(list, m, head-1);
    myQuickSort(list, head+1, n);
}

Answer 1

你的功能永远不会退出.

它将一直调用自己,直到调用堆栈已满并导致堆栈溢出异常.

编译器应该为此生成警告:

warning C4717: 'myQuickSort' : recursive on all control paths, function will cause runtime stack overflow

您需要一个退出条件,类似于:

void myQuickSort(int list[],int head, int tail)
{
    //exit condition, or else the function will always call itself
    if ( head >= tail )
       return;

    /**
    ...
    */

    myQuickSort(list, m, head-1);
    myQuickSort(list, head+1, n);
}

另外,请确保您调用以下函数:

int num[5] = {1,4,2,3,5};
myQuickSort(num,0,4);

最后的参数必须比数组的长度小1,因为C++数组是从0开始的.

您还需要在while循环中进行一次额外检查:

 while( head < tail && list[head] < key )  // see if head reached the end
 {
     ++head;
 }
 while( head < tail && list[tail] >= key )
 {
     --tail;
 }

否则你可能会传递数组的末尾.