C++ ⎼ 两个相似的函数，但表现却大不相同

Question

我正在编写一个快速排序程序。为此，我需要对数组进行分区。分区由函数 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;
}

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

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()

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

Answer 1

不同之处在于您在何处打破循环结构。

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

假设您已经在循环中迭代了一段时间。 (没有双关语意)。

你会点击这段代码:

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

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

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

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

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

这似乎就是区别所在。

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

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