extra-4

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int from, int end) {
        if (from >= end) {
            return;
        }

        int mid = doSort(nums, from, end);
        quickSort(nums, from, mid);
        quickSort(nums, mid + 1, end);
    }

    private int doSort(int[] nums, int from, int end) {
        int baseIndex = from + (int)(Math.random() * (end - from + 1));
        int base = nums[baseIndex];
        while (from <= end) {
            while (nums[from] < base) {
                from++;
            }

            while (nums[end] > base) {
                end--;
            }

            if(from == end)
                break;

            if (from < end) {
                int temp = nums[from];
                nums[from] = nums[end];
                nums[end] = temp;
                from++;
                end--;
            }
        }
        return end;
    }
}
//leetcode submit region end(Prohibit modification and deletion)