我正在编写一个快速排序程序。为此,我需要对数组进行分区。分区由函数 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()
之间的区别吗?
最佳答案
不同之处在于您在何处打破循环结构。
在您的代码中,您进行了两次条件检查,而在给定的代码中,您只进行了一次。
假设您已经在循环中迭代了一段时间。 (没有双关语意)。
你会点击这段代码:
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
循环直到它中断,但在您的代码中,您永远不会进入循环体。
关于C++ ⎼ 两个相似的函数,但表现却大不相同,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17949625/