0

我正在编写一个快速排序程序。为此，我需要对数组进行分区。分区是由一个函数完成的paritionIt()。我写了一个分区数组的代码，如下所示：

int partition(int beg,int end,double key)
{
    int pLeft = beg;
    int pRight = end-1;
    while(pLeft<pRight)
    {
        while(array[++pLeft]<key);
        while(array[--pRight]>key);
        if(pLeft<pRight)
            swap(pLeft,pRight);
    }
    swap(pLeft,end-1);
    return pLeft;
}

当单独执行时，这个块似乎可以正常工作。但是，当与其他函数一起运行时，它似乎会产生错误的答案。给我的以下代码使所有问题都消失了，但它与我的代码似乎没有太大区别。

int partitionIt(int left, int right, double pivot)
{
    int leftMark = left; //right of first elem
    int rightMark = right - 1; //left of pivot
    while(true)
    {
        while( theVect[++leftMark] < pivot ) //find bigger
        ; // (nop)
        while( theVect[--rightMark] > pivot ) //find smaller
        ; // (nop)
        if(leftMark >= rightMark) //if pointers cross,
            break; // partition done
        else //not crossed, so
            swap(leftMark, rightMark); //swap elements
    } //end while(true)
    swap(leftMark, right-1); //restore pivot
    return leftMark; //return pivot location
} //end partitionIt()

该块似乎与我的相似，但给出了正确的答案，而我的不是。你能告诉我有什么区别吗？partition()和之间有什么区别吗partitionIt()？

4

2 回答 2

1

我立即看到的唯一一件事是，如果使用以下命令调用，函数的行为会有所不同left + 1 == right：您的函数不会进入循环，但会返回beg；书中的函数将进入循环，因此 在进行最终交换和返回之前递增leftMark和递减。rightMarkleftMark

于 2013-07-30T14:36:40.747 回答
1

不同之处在于你打破循环结构的地方。

在您的代码中，您进行了两次条件检查，而在给定的代码中，您只进行了一次。

假设您已经在循环中迭代了一段时间。（没有双关语的意思）。

您将遇到以下代码：

 if(pLeft<pRight)
                swap(pLeft,pRight);

然后你会到达 while 循环的底部，回到顶部，然后再次检查 if pLeft<pRight。如果这不是真的，我们退出循环。

在给定的代码中，您执行交换，然后执行以下操作：

while( theVect[++leftMark] < pivot ) //find bigger
    ; // (nop)
    while( theVect[--rightMark] > pivot ) //find smaller
    ; // (nop)

然后你检查你是否跳出循环。

这似乎就是区别所在。

编辑：澄清 - 如果while(pLeft>=pRight)你第一次进入循环会发生什么？

在给定的代码中，您将继续while循环直到它中断，但在您的代码中，您永远不会进入循环体。

于 2013-07-30T14:31:14.723 回答