快速排序

class Solution {
    public int[] sortArray(int[] nums) {
	    // 区间 [0, nums.length - 1]
        quicksort(nums, 0, nums.length - 1);
        return nums;
    }
 
	// 区间 [left, right]
    private void quicksort(int[] nums, int left, int right) {
        if (left >= right) return;
        int num = partition(nums, left, right);
        quicksort(nums, left, num - 1);
        quicksort(nums, num + 1, right);
    }
 
    private int partition(int[] nums, int left, int right) {
        int base = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= base) { right--; } // 右边找到第一个小于 base 的数, 所以循环条件是 >=
            swap(nums, left, right);
            while (left < right && nums[left] <= base) { left++; }   // 左边找到第一个大于 base 的数, 所以循环条件是 <=
            swap(nums, left, right);
        }
        return left;
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}