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

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

  •  
  •   nnegier · 2019-08-08 21:31:43 +08:00 · 2818 次点击
    这是一个创建于 1693 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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;
    	}
    
    10 条回复    2019-08-10 01:01:58 +08:00
    monstervivi
        1
    monstervivi  
       2019-08-08 21:52:46 +08:00
    感觉你这算法写的不好,建议网上找一下别的快速排序算法

    自推一下我总结写的
    https://github.com/monsterhxw/Sorting-Algorithm-Practice/blob/master/QuickSort/main.c
    smdbh
        2
    smdbh  
       2019-08-08 22:24:03 +08:00
    你说的对,是错的
    carlclone
        3
    carlclone  
       2019-08-08 22:39:49 +08:00
    奇怪的写法 , pivot 一般是数组某个元素的下标吧
    nnegier
        4
    nnegier  
    OP
       2019-08-09 00:23:10 +08:00 via Android
    @carlclone 这个不影响
    versionlin
        5
    versionlin  
       2019-08-09 00:41:49 +08:00
    循环完成后要交换 pivot 和指针所指位置的元素,所以 pivot 一般是数组某个元素的下标。
    nomoon
        6
    nomoon  
       2019-08-09 01:00:51 +08:00
    你在 swap 后面加上 leftPtr--; rightPtr++;就好了
    nnegier
        7
    nnegier  
    OP
       2019-08-09 09:21:14 +08:00 via Android
    @nomoon 我怎么没想到呢,这个可以。
    nnegier
        8
    nnegier  
    OP
       2019-08-09 13:42:26 +08:00 via Android
    @nomoon No,这样增加了比较次数,我刚刚解决了,有更好更简单的方式(不过还是谢谢)
    nnegier
        9
    nnegier  
    OP
       2019-08-09 14:36:23 +08:00
    @nomoon 话收回收回,没有增加比较次数。我的算是您想法的改进版本。谢谢谢谢
    nomoon
        10
    nomoon  
       2019-08-10 01:01:58 +08:00
    @nnegier 哈哈。。解决就好。。。不谢~~~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3101 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:43 · PVG 20:43 · LAX 05:43 · JFK 08:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.