快速排序,眉庄说这个思路是极好的,可惜就是死了个循环TUT(java)

亡灵S 发布于 2013/07/30 15:51
阅读 633
收藏 1

我感觉我挺有思路的啊,怎么就是不对呢?!

public class quickSort {
	public static void qs(int[] a,int i,int j)
	{

	if(i<j)
	{
		
		int tempt=0;
		int key=a[i];
		int s=i;
		int e=j;
		
		while(s<e)
		{
		
			while(a[s]<=key&&s<e)
			{
				s++;
			}
			while(a[e]>=key&&e>s)
			{
				e--;
			}
			tempt=a[s];
			a[s]=a[e];
			a[e]=tempt;
			
			if(s==e)
			{
				tempt=a[i];
				a[i]=a[s];
				a[s]=tempt;
			}
			
			
			
		}
		int mid=s;
		qs(a,0,mid-1);
		qs(a,mid+1,a.length-1);
	}
		
	
		
	}

	public static void main(String[] args) {
		int[] a={2,6,0,3,5,7,67,10,1,35,23,8,24};
		//int[] a={2,1,3};
	
		int i=0,j=a.length-1;
		qs(a,i,j);
			
		for(i=0;i<=a.length-1;i++)
		{
			System.out.print(a[i]+",");
		}

	}

}

加载中
1
lock_free
lock_free
package tech.algorithms.sort;

import java.util.Random;



public class QuickSort {  
	  
    public static void main(String[] args) {  
//         int[] array = { 13, 13, 13, 13, 13, 13, 13, 13, 13,13 };  
//         int[] array = { 13, 19, 9, 5, 1, 2, 8, 7, 4, 23, 2, 6, 11 };  
        int[] array = new int[10000];  
        Random r = new Random();  
        for (int i = 0; i < array.length; i++) {  
            array[i] = r.nextInt(100);  
        }  
        QuickSort qs = new QuickSort();  
  
        qs.sort(array, 0, array.length - 1);  
  
        for (int loopIndex = 0; loopIndex < array.length; loopIndex++) {  
            System.out.println(array[loopIndex]);  
        }  
    }  
  
    private void sort(int[] array, int bottom, int top) {  
        if (bottom < top) {  
            int divdePoint = partition(array, bottom, top);  
            sort(array, bottom, divdePoint - 1);  
            sort(array, divdePoint + 1, top);  
        }  
  
    }  
  
    private int partition(int[] array, int bottom, int top) {  
  
        int divideValue = array[top];  
  
        int i = bottom;  
        for (int loopIndex = bottom; loopIndex <= top; loopIndex++) {  
            if (array[loopIndex] < divideValue) {  
                int temp = array[loopIndex];  
                array[loopIndex] = array[i];  
                array[i] = temp;  
                i++;  
            }  
        }  
  
        int temp = array[top];  
        array[top] = array[i];  
        array[i] = temp;  
  
        return i;  
    }  
}
亡灵S
亡灵S
不知道该说什么好了,通过您的这段代码我终于意识到了,代码效率的问题,非常非常的感谢:)好厉害!PS:太开心了,找到了问题所在还看到这么高效的代码,我的代码改完之后利用你的那个10000个随机数的办法,结果我都看完好几话漫画他都没运行完TUT哈哈,太开心了!
1
Alexander_zhou
Alexander_zhou

问题出在第 28 行,此时,a[s] 可能小于等于 a[i],也可能大于 a[i],需要判断后进行相应处理(比如当 a[s] 小于等于 a[i] 时,交换两者;当 a[s] 大于 a[i] 时,将 a[s-1] 与 a[i] 交换)。

总之,这样修修补补的结果是:效率不高,而且可能存在 Bug。

亡灵S
亡灵S
确实,是你说的那个问题,你们发现问题貌似都是直接看代码就想出来的,悲剧的,我是用笔算的o(╯□╰)o我后来在if(s==e&&a[i]>a[s])加了个a[i]>a[s]就好了,但是效率很低,效率比较好的是袁前辈和封前辈那两个PS:袁前辈的那个是在我的代码基础上改的,所以效率不如封前辈那个。
1
袁不语
袁不语
39        qs(a,0,mid-1);

40      qs(a,mid+1,a.length-1);

这两行有问题。

应该这样:

39      qs(a,i,mid-1);

40      qs(a,mid+1,j);

亡灵S
亡灵S
回复 @袁不语 : 我怎么就没想到把那两个while换下位置呢!!!我是通过笔在纸上模拟了一遍过程结果和程序运行的不符,才发现问题所在,于是我便if(s==e&&a[i]>a[s]),甚至特意考虑了一下用不用添加a[i]<a[e](结果发现没必要)。。而且这样的话效率得到了很大的提高:)谢谢!!!!如果能选两个最佳就好了!PS:果然我脑子不灵光啊,用脑子想怎么都感觉自己对- -
袁不语
袁不语
还有16-19 与 20-23 换一下顺序。
0
chuangyu
chuangyu

闲得蛋疼看了下程序,算法有问题。

你自己想办法描述一下你的算法就能知道问题在哪里了。

0
亡灵S
亡灵S

引用来自“cyZhu”的答案

闲得蛋疼看了下程序,算法有问题。

你自己想办法描述一下你的算法就能知道问题在哪里了。

想了想,还是感觉挺对的orz【虽然我知道肯定是错了】

s从左扫描遇到大于key的跳出循环,接着来用e从后向前扫,遇到小于key的跳出循环,a[s]与a[e]交换。当s==e时,a[i](即key)与a[s]相交换,当i>j时不再进行递归调用。。。

0
chuangyu
chuangyu

代码里选择key的方式和a[s]和a[e]的交换有点无厘头。

或者说,你想得很好,但是你的代码和你的想法是不一样的。

亡灵S
亡灵S
谢谢您的热心回复:)
0
chuangyu
chuangyu

从代码上看,a[s]和a[e]交换的目的是为了使小的放前面,这时key就应该取中值,并且要使得key是在a[s]与a[e]之间,但代码里key始终取范围[i,j]内的第一个值。

就是个精虫上脑的地方
就是个精虫上脑的地方
key值确实是取第一个值 不是取中值 key只是一个参考 不是序列的中间值
0
就是个精虫上脑的地方
就是个精虫上脑的地方
(a[s]<=key&&s<e)这个判断不对 开始时key=2 s++=1 循环一次条件不满足 此时s=1 第一步应该是2和6换位置 然后1和2换位置 你的逻辑不对 应该是for循环里放判断
亡灵S
亡灵S
谢谢您的热心回复:)PS:错的地方是if(s==e&&a[i]>a[s])//(s==e)
0
王瑞平
王瑞平
   if(i<j)
06     {
07          
08         inttempt=0;
09         intkey=a[i];
10         ints=i;
11         inte=j;
12          
13         while(s<e)
14         {
0
王瑞平
王瑞平
永远对,循环不可能处得来
亡灵S
亡灵S
谢谢您的热心回复:) PS:循环可以出来的
返回顶部
顶部