背快排采坑问题

快排是个满基础的排序算法,网上的教程铺天盖地。也很好理解。
理解了算法,背代码也特别简单。(这种东西写多了,有时候有点茫然是自己真会了还是自己背会了,后来我觉得这事儿挺简单的:数学发展了这么多年,就这么几个经典算法,前数学家们的匠心巨作,我要是能盲做出来,自己也就成数学家了。于是不再纠结自己是背会了还是真会了)
但是,有一天,我默写默错了。
那个特别x疼的牛客网又没有断点调试,我推导了半天自己哪儿写错了,按理是边界条件,但哪个边界我觉得我都没错。我把我当时的代码贴出来。

public class Main {
    public static void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
       int i=left,j=right,temp = arr[left];
       
       while(i<j){
           while(arr[i]<=temp && i<j){
               i++;
           }
           while(arr[j]>=temp && i<j){
               j--;
           }
           if(i<j){
               int temp1 = arr[j];
               arr[j] = arr[i];
               arr[i] = temp1;
           }
            
       }
       arr[left] = arr[i];
       arr[i] = temp;
        
       quickSort(arr,left,i-1);
       quickSort(arr,i+1,right);
       
        
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2,3,1,9,4,10,6};
       quickSort(arr,0,4);
        for(int a:arr){
            System.out.println(String.valueOf(a));
        }
        
        System.out.println("Hello World!");
    }
}

我当时很快速得默完了,我觉得妥妥的,结果一跑main,结果不对,自己心里推导了一下,发现每轮都有一个边界没有被排到顺序,但光肉眼看,真是看不出问题在哪儿。等完后我比对了下代码,发现问题在这里

          while(arr[i]<=temp && i<j){
               i++;
           }
           while(arr[j]>=temp && i<j){
               j--;
           }

这个地方正确的顺序是

          while(arr[j]>=temp && i<j){
               j--;
           }
          while(arr[i]<=temp && i<j){
               i++;
           }

这个东西,真是- -。。太细微了。主要问题出在这个i轴上,如果顺序错误,出了大循环后,基准点要和i轴位置的数互换,会导致换错位。因为无论给的数组数据如何,大while里面的小while,按错误顺序运行的话,总会走i++,这肯定是不对的。
好了,复盘就到这里吧。为此次失误感到心塞。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容