iteye_169 2011-04-08 18:26
浏览 255
已采纳

这个蛋疼的随机产生结果的快速排序

 

public static void quickSort2(int[] sourse, int low, int high)
    {   
        if(low>high)
            return;
        int pivot=sourse[low];
        int i=low;
        int j=high;
        if(i<j)
        {
            while(i<j)
            {
                while(sourse[i]<pivot&&i<high)
                {
                    i++;
                }
                while(sourse[j]>pivot&&j>low)
                {
                    j--;
                }
                if(i<j)
                {
                    swap(sourse,i,j);
                }
            }
            if(i>j)
                swap(sourse,low,j);
            
            quickSort2(sourse,low,j-1);
            quickSort2(sourse,j+1,high);
        }
    }
    
    public static void main(String[] args)
    {
        int[] sourse ;
        
        sourse=new int[]{1,23,5,-2,-45,73,9,4,7,12,47,126,0,71,40,51,99};
        quickSort2(sourse, 0, sourse.length-1);
        System.out.println("快速排序:");
        printArray(sourse);// 输出到转后数组的值
        
        
    }

 
以上是自己写的一个快速排序的函数,小测了一下,第一次可以正确执行,第二次CPU就卡在50%,有时候还会报越界错误,真不知道是咋回事?排除了一下是不是因为数组长度太大的问题,但好像与这个没有必然联系,虽然大的时候更容易错。

现在测试,又正常了,悲勒个剧的,难道还有随机性?!
有木有同学可以帮忙挑一下刺儿的,分析一下代码哪里不太合适?

 

ps:谢谢一楼的回复,三楼有正确答案,这个快速排序和书上一般见到的不太一样,自己看吧。

 


问题补充
好,我改改看
问题补充

改好后的,注意判断等号,i<j,i==j时的基准与sourse[i]大小的问题:

 

public static void quickSort2(int[] sourse, int low, int high)
    {   
        //System.out.println("基准值:"+sourse[low]);
        int i=low;
        int j=high;
        if(i<j)
        {   
            int pivot=sourse[low];
            while(i<j)
            {
                
                while(sourse[i]<= pivot&&i<j)
                {
                    i++;
                }
                while(sourse[j]>pivot&&i<j)
                {
                    j--;
                }
                if(i<j)
                {
                    swap(sourse,i,j);
                }

            }
            
            if(pivot<sourse[i])
                 i--;
            
            swap(sourse,low,i);
            
            
            quickSort2(sourse,low,i-1);
            quickSort2(sourse,i+1,high);
        }
    }
public static void main(String[] args)
    {
        int[] sourse ;
        
        sourse = createArray(20);
        //sourse=new int[]{1,23,5,-2,-45,73,9,4,7,12,47,126,0,71,40,51,99,99,40,7,12,126};
        quickSort2(sourse, 0, sourse.length-1);
        System.out.println("快速排序:");
        printArray(sourse);// 输出到转后数组的值
        
        
    }

 
问题补充
其它的我都实现了,就是自己写快速时碰到了问题,还是写代码不够仔细

  • 写回答

2条回答

  • adri1 2011-04-08 18:26
    关注

    对相等的处理有问题导致了死循环

    每次递归的第一次 sourse[i]总是等于pivot 无意义

    另外一开始有个if(low>high)的判断

    后边为啥还要有if(i<j) 而且还漏掉了=

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥20 Python安装cvxpy库出问题
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题