public class Test {
static int[] theArray = {25,6,5,88,56,989,41,12,34,65};
public static void main(String[] args) {
partionIt(0, theArray.length-1, 88);
for (int i = 0; i < theArray.length; i++) {
System.out.print(theArray[i]+" ");
}
System.out.println();
}
public static int partionIt(int left,int right,int pivot) {
int leftPtr = left - 1;
int rightPtr = right + 1;
while (true) {
while (leftPtr<right&&theArray[++leftPtr]<pivot)
;
while (rightPtr>left&&theArray[--rightPtr]>pivot)
;
if (leftPtr>=rightPtr) {
break;
}else {
swap(leftPtr, rightPtr);
}
}
return leftPtr;
}
public static void swap(int index1,int index2) {
int temp = theArray[index1];
theArray[index1] = theArray[index2];
theArray[index2] = temp;
}
}
我选的比较值是 88,划分的意思就是小的在一边,大的在一边。
这是输出结果:
25 6 5 65 56 34 41 12 989 88
很明显正确的结果是 989 应该在 88 的右边。
我知道出现这个错误的原因,是因为里面第一个 while 就找到了 88,然后就和第二个 while 找到的最右边那个小于 88 的交换了,然后就再也没有比较它了,所以 88 就一直在最右边了。
这个算法是在《 Java 数据结构和算法》上看到的,代码就这样,一点没有变啊,我刚刚还确认了一下。当然比较值 pivot 换成最大值右边的数值比如 41,这个算法还是运行良好的。但是书上也没有特别指明呀。
所以,这个算法做划分本身是错误的?
求解