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,这个算法还是运行良好的。但是书上也没有特别指明呀。
所以,这个算法做划分本身是错误的?
求解
改成这样即可
public static int partionIt(int left,int right,int pivot) {
int leftPtr = left;
int rightPtr = right;
while (true) {
while (leftPtr<right&&theArray[leftPtr]<pivot)
leftPtr++;
while (rightPtr>left&&theArray[rightPtr]>pivot)
rightPtr--;
if (leftPtr>=rightPtr) {
break;
}else {
swap(leftPtr, rightPtr);
}
}
return leftPtr;
}
1
monstervivi 2019-08-08 21:52:46 +08:00
感觉你这算法写的不好,建议网上找一下别的快速排序算法
自推一下我总结写的 https://github.com/monsterhxw/Sorting-Algorithm-Practice/blob/master/QuickSort/main.c |
2
smdbh 2019-08-08 22:24:03 +08:00
你说的对,是错的
|
3
carlclone 2019-08-08 22:39:49 +08:00
奇怪的写法 , pivot 一般是数组某个元素的下标吧
|
5
versionlin 2019-08-09 00:41:49 +08:00
循环完成后要交换 pivot 和指针所指位置的元素,所以 pivot 一般是数组某个元素的下标。
|
6
nomoon 2019-08-09 01:00:51 +08:00
你在 swap 后面加上 leftPtr--; rightPtr++;就好了
|