c - 快速排序逻辑无法正常工作

Question

以下是我制作的快速排序代码。但是有一些问题，这给了我错误的输出。对于整数数组 [65,70,75,80,85,60,55,50,45]，我得到的输出是[45 50 55 65 60 70 75 80 85]，这显然是错误的。

int partition(int *b,int r,int s)
{
    int pivot=b[r];
    int i,j;
    i=r;
    j=s;
    while(i<=j)
    {
        while(b[i]<=pivot)
            i++;
        while(b[j]>=pivot)
            j--;
        if(i<j)
        {
            int temp;
            temp=b[i];
            b[i]=b[j];
            b[j]=temp;
        }
    }
    b[r]=b[j];
    b[j]=pivot;
    return j;
}
void quicksort(int *a,int p,int q)
{

    if(p<q)
    {
        int j;
        j=partition(a,p,q);
        quicksort(a,p,j-1);
        quicksort(a,j+1,q);

    }
}
int main()
{
    int arr[9]={65,70,75,80,85,60,55,50,45};
    quicksort(arr,0,8);
    for(int i=0;i<9;i++)
        printf("%d ",arr[i]);
    getch();
    return 0;
}

有人可以指出我的错误吗？

Answer 1

您应该检查自己没有出界。我也认为你应该使用严格的比较。您当前的代码将无法对 [1, 2] 进行排序(最后一次交换会将其搞乱)。

最后的交换看起来有点随意，不需要。