美文网首页
快速排序 Java

快速排序 Java

作者: 楼主楼主 | 来源:发表于2018-05-24 16:37 被阅读0次
    public void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
    }
    private void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int target =arr [left];
        int i = left;
        int j = right;
        while(i<j){
            //以左侧为基准开始排序,则必须右侧先开始移动指针,这样最后到达的位置是小于基准值的 方便基准值归位中间
            //右侧arr[j]>target,左侧arr[i]<=target,这样保证在基准值的左侧是小于等于,右侧是大于
            while(i<j && arr[j]>target){
                j--;
            }
            while(i<j && arr[i]<=target){
                i++;
            }
            if(i<j){
                int tmp = arr[i];
                arr[i]=arr[j];
                arr[j]=tmp;
            }
        }
        // 此时 指针i所指向的值一定是小于或等于 target的,交换target 和 arr[i],保证左侧均为小于或等于target
        arr[left]=arr[i];
        arr[i]=target;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
    

    相关文章

      网友评论

          本文标题:快速排序 Java

          本文链接:https://www.haomeiwen.com/subject/azmsjftx.html