2 
#include <stdio.h>


int Partition (int * A, int p, int r)
{
    printf("PARTITION\n");
    int x=0;
    x=A[r];
    int i=p-1, j=r+1;
    int temp;
    int k=0;
    while(1)
    {
        printf("\tLOOP\n");
        do
        {
            j=j-1;
        } while(A[j]>x) ;

        do
        {
            i=i+1;
        } while(A[i]<x);

        if (i<j)
        {
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
        else
        {
            printf ("ARRAY: ");
            for (k=p; k<=r; k++)
                printf ("%d,",A[k]);
            printf ("\nRETURNING : %d \n", j);

            return j;
        }

    }
}
void QuickSort(int * A, int p, int r)
{
    int q;
    if (p<r)
    {
        q = Partition (A,p,r);
        QuickSort(A,p,q);
        QuickSort(A,q+1,r);
    }

}



int main()
{
    int A[9] = {9,2,4,1,7,8,3,5,6};
    int i;
    QuickSort(A,0,8);
    for (i=0;i<=8;i++)
    {
        printf("%d ", A[i]);
    }
    return 0;
}

在 GDB 上一个小时后，我把这个程序的问题缩小到了：

我的数组有从 0-9 的索引。它首先被划分为 0-5 和 6-9。然后 0-5 部分被划分为 0-2 和 3-5 然后 0-2 部分被划分为 0-0 和 1-2 现在 0-0 部分由于if (p<r)条件而被跳过，但程序调用 Partition (A,1,2) 为另一部分。现在这是程序卡住的地方，它一次又一次地调用 Partition (A,1,2)，因为它一直返回 '2' 作为枢轴索引。

为什么会这样？我无法理解程序逻辑上哪里出错了，我遵循了互联网上各个地方给出的确切伪代码。

编辑：我能够通过使用if (i<=j)而不是if (i<j)in来解决问题Partition。它迫使j再次递减，但这只是因为我很幸运选择do while了而不是while. 我仍然不明白为什么直接实现 Quicksort 伪代码不起作用。

4

1 回答 1

1

您在代码中犯了很多错误。

  • QuickSort(A,p,q);是QuickSort(A,p,q-1)；

  • int i=p-1, j=r+1;没有必要。

  • 您的partition(), 将需要一个额外的变量来保存枢轴。

  • while(A[i]<x) ;应该是while(A[i] <= x[piv] && i<r )；

  • 在您的程序中，您错过了一个算法步骤，其中枢轴处的数组变量与您的最后一个数组变量交换，没有这个关键步骤，就不会发生排序。

这是您的程序，并进行了更正

#include <stdio.h>


int Partition (int  *A, int p, int r)
{
    printf("PARTITION\n");
    int i=p, j=r ,piv=p ;
    int temp;

    while(i<j)
    {
        printf("\tLOOP\n");

       while(A[i] <= A[piv] && i<r)
           i++;

       while(A[j]>A[piv]) 
           j--;


            if (i<j)
            {
                temp=A[i];
                A[i]=A[j];
                A[j]=temp;
            }
    }

/*Crucial step that you happen to miss*/
         temp=A[piv];
         A[piv]=A[j];
         A[j]=temp;

return j;
}


void QuickSort(int *A, int p, int r)
{
    int q;
    if (p<r)
    {
        q = Partition (A,p,r);
        QuickSort(A,p,q-1);
        QuickSort(A,q+1,r);
    }
}



int main()
{
    int A[9] = {9,2,4,1,7,8,3,5,6};
    int i;
    QuickSort(A,0,8);
    for (i=0;i<=8;i++)
    {
        printf("%d ", A[i]);
    }
    return 0;
}
于 2013-03-15T12:15:13.027 回答