c - 我机器上的 QuickSort 段错误

Question

#include<stdio.h>
int partition(int p[],int lb,int ub)
{

    int i,temp,up,down,pivot;

    pivot=p[lb];
    up=ub;
    down=lb;

    while(down<up)
    {
        while(p[down]<=pivot&&down<ub)
        down++;
        while(p[up]>pivot)
        up--;
        if(down<up)   //exchange them
        {
            temp=p[down];
            p[down]=p[up];
            p[up]=temp;

        }
    }
        temp=p[lb];
    p[lb]=p[up];
    p[up]=temp;
return up;

}
void myqsort(int a[], int lb,int ub)
{
int q=partition(a,lb,ub);
myqsort(a,lb,q-1);
myqsort(a,q+1,ub);
}
int main()
{
int m[]={1,2,5,6,3};
for(int i=0;i<5;i++)
printf("%d",m[i]);
myqsort(m,0,4);
for(int i=0;i<5;i++)
printf("%d",m[i]);
return 0;
}

上面的代码给出了一个段错误。它是我在 c 中实现的递归快速排序。查看了其他答案，但它们没有解决我的问题。知道出了什么问题吗？知道我做错了什么吗？

Answer 1

当我 gdb 编辑您的代码时，堆栈跟踪变得很糟糕。

#0  partition (p=0xbffff8a4, lb=0, ub=-174722) at qs.c:3
#1  0x08048525 in myqsort (a=0xbffff8a4, lb=0, ub=-174722) at qs.c:33
#2  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174721) at qs.c:34
#3  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174720) at qs.c:34
#4  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174719) at qs.c:34
#5  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174718) at qs.c:34
#6  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174717) at qs.c:34
#7  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174716) at qs.c:34
#8  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174715) at qs.c:34
#9  0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174714) at qs.c:34
#10 0x08048540 in myqsort (a=0xbffff8a4, lb=0, ub=-174713) at qs.c:34
....

myqsort 函数无限递归。

你应该在 myqsort 中添加两行

void myqsort(int a[], int lb,int ub)
{
    if (lb >= ub)
        return;
    int q=partition(a,lb,ub);
    myqsort(a,lb,q-1);
    myqsort(a,q+1,ub);
}