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

// arr[1..r]排好序
public static void quickSort(int[] arr, int L, int R) {
    if (L < R) {
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0] - 1); //<區(qū)
        quickSort(arr, p[1] + 1, R); //>區(qū)
    }
}

public static int[] partition(int[] arr, int L, int R) {
    int less = L- 1; //<區(qū)右邊界
    int more = R;//>區(qū)左邊界
    while (L < more) { // L表示當(dāng)前數(shù)的位置 arr[R]-> 劃分值
        if (arr[L] < arr[R]) { // 當(dāng)前數(shù) < 劃分值
            swap(arr, ++less, L++);
        } else if (arr[L] > arr[R]) {  // 當(dāng)前數(shù) > 劃分值
            swap(arr, --more, L);
        } else{
            L++;
        }
    }
    swap(arr,more,R);
    return new int[] { less + 1, more };
}

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