这个划分算法,是不是整体就是错的呀

2019-08-08 21:31:43 +08:00
 nnegier
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,这个算法还是运行良好的。但是书上也没有特别指明呀。

所以,这个算法做划分本身是错误的?

求解

2954 次点击
所在节点    算法
10 条回复
monstervivi
2019-08-08 21:52:46 +08:00
感觉你这算法写的不好,建议网上找一下别的快速排序算法

自推一下我总结写的
https://github.com/monsterhxw/Sorting-Algorithm-Practice/blob/master/QuickSort/main.c
smdbh
2019-08-08 22:24:03 +08:00
你说的对,是错的
carlclone
2019-08-08 22:39:49 +08:00
奇怪的写法 , pivot 一般是数组某个元素的下标吧
nnegier
2019-08-09 00:23:10 +08:00
@carlclone 这个不影响
versionlin
2019-08-09 00:41:49 +08:00
循环完成后要交换 pivot 和指针所指位置的元素,所以 pivot 一般是数组某个元素的下标。
nomoon
2019-08-09 01:00:51 +08:00
你在 swap 后面加上 leftPtr--; rightPtr++;就好了
nnegier
2019-08-09 09:21:14 +08:00
@nomoon 我怎么没想到呢,这个可以。
nnegier
2019-08-09 13:42:26 +08:00
@nomoon No,这样增加了比较次数,我刚刚解决了,有更好更简单的方式(不过还是谢谢)
nnegier
2019-08-09 14:36:23 +08:00
@nomoon 话收回收回,没有增加比较次数。我的算是您想法的改进版本。谢谢谢谢
nomoon
2019-08-10 01:01:58 +08:00
@nnegier 哈哈。。解决就好。。。不谢~~~

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/590292

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX