快排.md

快排

    public static void swap(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    //对一个数组，实现小于等于某个数的值在前面，大于的在后面
    public static void splitNum(int[] arr){
        int lessEqualR=-1;
        int index=0;
        int N=arr.length;
        while(index<N){
            if(arr[index]<=arr[N-1]){
                swap(arr,++lessEqualR,index++);
            }
            else{
                index++;
            }
        }
    }
    //对一个数组，实现小于在前面，等于在中间，大于在后面
    public static void splitNum2(int[] arr){
        int N=arr.length;
        int lessR=-1;
        int moreL=N-1;
        int index=0;
        while(index<moreL){
            if(arr[index]<arr[N-1]){
                swap(arr,index++,++lessR);
            }
            else if (arr[index]==arr[N-1]) {
                index++;
            }
            else{
                swap(arr,index,--moreL);
            }
        }
        swap(arr,N-1,moreL);
    }
    public static int[] partition(int[] arr,int L,int R) {
        int Less = L - 1;
        int More = R;
        int index = 0;
        while (index < More) {
            if (arr[index] > arr[R]) {
                swap(arr, index, --More);
            } else if (arr[index] == arr[R]) {
                index++;
            } else {
                swap(arr, index++, ++Less);
            }
        }
        swap(arr, More, R);
        return new int[]{Less+1,More};
    }
    public static void process(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        int[] equal=partition(arr,L,R);
        process(arr,L,equal[0]-1);
        process(arr,equal[1]+1,R);
    }
    public static void quicksort(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        process(arr,0,arr.length-1);
    }