快速排序模版

    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = nums[left];
        int i = left - 1, j = right + 1;
        while (i < j) {
            // 这两个while循环的顺序可以交换，顺序不重要
            while (nums[--j] > pivot) {
            }
            while (nums[++i] < pivot) {
            }
            if (i < j) {
                swap(nums, i, j);
            }
        }
        // 关键点是怎么切分，当退出循环后
        // nums[j]左边的数都小于pivot，nums[i]右边的数都大于pivot
        // 而i和j的关系有两种，要么i=j，要么i=j+1
        // 所以切分时可以用[left,i-1][i,rigjt]，和[left,j][j+1,right]这两种
        // 而我们选取的pivot是最左边的数，当pivot一开始就处于正确的位置，即此时i=left时
        // 这时按[left,i-1][i,rigjt]切分就会出现死循环，第二段区间依然是[left, right]
        // 故当我们选取left为pivot时，需要用[left,j][j+1,right]来切分
        // 同理，当我们选取最后一个值为pivot时，需要用i来切分，防止j的位置不变，导致死循环
        quickSort(nums, left, j);
        quickSort(nums, j + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }