我正在编写一个快速排序程序。为此，我需要对数组进行分区。分区由一个函数完成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()。
区别在于您要突破循环结构。
在您的代码中，您进行了两个条件检查，而在给定的代码中，您仅进行了一个条件检查。
假设您已经在循环中迭代了一段时间。（无双关语意）。
您将点击以下代码：
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循环直到中断为止，但是在您的代码中，您永远不会进入循环的主体。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句