首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  算法

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

  •  
  •   nnegier · 97 天前 · 979 次点击
    这是一个创建于 97 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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 条附言  ·  96 天前

    改成这样即可

    	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;
    	}
    
    10 回复  |  直到 2019-08-10 01:01:58 +08:00
        1
    monstervivi   97 天前
    感觉你这算法写的不好,建议网上找一下别的快速排序算法

    自推一下我总结写的
    https://github.com/monsterhxw/Sorting-Algorithm-Practice/blob/master/QuickSort/main.c
        2
    smdbh   97 天前
    你说的对,是错的
        3
    carlclone   97 天前
    奇怪的写法 , pivot 一般是数组某个元素的下标吧
        4
    nnegier   97 天前 via Android
    @carlclone 这个不影响
        5
    versionlin   97 天前
    循环完成后要交换 pivot 和指针所指位置的元素,所以 pivot 一般是数组某个元素的下标。
        6
    nomoon   97 天前
    你在 swap 后面加上 leftPtr--; rightPtr++;就好了
        7
    nnegier   96 天前 via Android
    @nomoon 我怎么没想到呢,这个可以。
        8
    nnegier   96 天前 via Android
    @nomoon No,这样增加了比较次数,我刚刚解决了,有更好更简单的方式(不过还是谢谢)
        9
    nnegier   96 天前
    @nomoon 话收回收回,没有增加比较次数。我的算是您想法的改进版本。谢谢谢谢
        10
    nomoon   96 天前
    @nnegier 哈哈。。解决就好。。。不谢~~~
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2446 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 00:37 · PVG 08:37 · LAX 16:37 · JFK 19:37
    ♥ Do have faith in what you're doing.