package Test01;

public class QuickSprt {

    public static void main(String[] args) {
        int[] arr = { 1, 3, 2, 9, 8, 7, 1, 0,0,2,3,3,1,0,101,100,1,1,001,100 }; // 要排序的数组
    

        QuickSort(arr);
        for (int i : arr) {
            System.out.print(i+"  ");
        }
    }

    public static void QuickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        } else {
            quickSort(arr, 0, arr.length - 1);
        }

    }

    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0] );
            quickSort(arr, p[1] , R);
        
        }
    }

    public static int[] partition(int[] arr, int L, int R) {
        int num = arr[(int) (Math .random()*(R-L+1)+L)];  //随机快排
        int less = L - 1;
        int more = R + 1;
        while (L < more) {
            if (arr[L] < num) {
                swap(arr, L++, ++less);

            } else if (arr[L] > num) {
                swap(arr, L, --more);

            } else {
                L++;
            }
        }
        return new int[] { less, more };

    }
    
    public static void swap(int arr[], int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;

    }
}