这是一个创建于 1965 天前的主题，其中的信息可能已经有所发展或是发生改变。
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，这个算法还是运行良好的。但是书上也没有特别指明呀。
所以，这个算法做划分本身是错误的？
求解
第 1 条附言 · 2019-08-09 14:14:58 +08:00
改成这样即可
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++;就好了
|
Select Language