// 这个函数就是查找到arr[l]位置应该处于什么位置
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        int j = l;
        for(int i = l + 1; i <= r; i++) {
            if(arr[l].compareTo(arr[i]) > 0) { // i位置的元素小于当前元素
                j ++;
                // 交换j和i的位置
                swap(arr, j, i);
            }
        }
        // 当i遍历完后，交换j和l的位置。
        swap(arr, j, l);
        // 最后返回j的下标
        return j;
    }
    // 交换数组中两个元素
    private static <E> void swap(E[] arr, int j, int i) {
        E temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

// 这个函数就是查找到arr[l]位置应该处于什么位置
    // 循环不变量：arr[l + 1...j] < v; arr[j + 1...i] >= v;
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        // j = l;
        // 随机化一个下标，防止每次都使用第一个元素作为基准。对于有序数组，那么他的时间复杂度就变为o(n2)
//        int randomIndex = (int) Math.floor(Math.random() * (r - l + 1)) + l;
      +  int randomIndex = (new Random()).nextInt(r - l + 1) +l;
      +  swap(arr, randomIndex, l);
        int j = l;
        for(int i = l + 1; i <= r; i++) {
            if(arr[l].compareTo(arr[i]) > 0) { // i位置的元素小于当前元素
                j ++;
                // 交换j和i的位置
                swap(arr, j, i);
            }
        }
        // 当i遍历完后，交换j和l的位置。
        swap(arr, j, l);
        // 最后返回j的下标
        return j;
    }

private static <E extends Comparable<E>> int partition2(E[] arr, int l , int r) {
//        int randomIndex = (new Random()).nextInt(r - l + 1) + l;
        int randomIndex = (int) Math.floor(Math.random() * (r - l + 1)) + l;
        swap(arr, randomIndex, l);
        int i = l + 1;
        int j = r;
        while(true) {
            // i未超界，并且元素小于标注数
            while(i <= j && arr[i].compareTo(arr[l]) < 0) {
                i++;
            }
            // j未超界，并且元素大于标注数
            while(j >= i && arr[j].compareTo(arr[l]) > 0) {
                j--;
            }
            // 越界，跳出循环。
            if(i >= j) break;
            // 上面i, j下标都暂停，那么交换两个位置的元素
            swap(arr, i, j);
            i++;
            j--;
        }
        // 最后交换l和j的位置
        swap(arr, l, j);
        return j;
    }
    // 交换数组中两个元素
    private static <E> void swap(E[] arr, int j, int i) {
        E temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

public static <E extends Comparable<E>> void sort3(E[] arr, int l, int r) {
        if(l >= r) {
            return;
        }
        int randomIndex = (new Random()).nextInt((r - l + 1)) + l;
        swap(arr, l, randomIndex);
        // 循环不变量 arr[l ... lt - 1] < v ; arr[lt ... gt - 1] == v ; arr[gt ... r] > v;
        // 开始的时候区间元素都为空
        int lt = l, i = l + 1, gt = r + 1;
        while(i < gt) { // 当i 和 gt重合时
            if(arr[l].compareTo(arr[i]) < 0) { // 交换gt和i的位置
                gt--;
                swap(arr, i, gt);
            }else if(arr[l].compareTo(arr[i]) > 0) { // 交换lt和i的位置
                lt++;
                swap(arr, lt, i);
                i++;
            }else { // 二者相等，i直接++
                i++;
            }
        }
        // 交换二者位置。 l, lt
        swap(arr, l, lt);
        sort3(arr, l, lt - 1);
        sort3(arr, gt, r);
    }
    // 交换数组中两个元素
    private static <E> void swap(E[] arr, int j, int i) {
        E temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

class Solution {
        public void sortColors(int[] nums) {
            // nums[0 ... zero] == 0; nums[zero +1, i] == 1; nums[two, n - 1] == 2;
            int zero = -1, i = 0, two = nums.length;
            while(i < two) {
                if(nums[i] == 0) {
                    zero ++;
                    swap(nums, zero, i);
                    i++;
                }else if(nums[i] == 2) {
                    two --;
                    swap(nums, i, two);
                }else { // nums[i] == 1
                    i++;
                }
            }
        }
        private void swap(int [] nums, int i, int j ) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }