912 quick sort

别忘了基础呀

class Solution {
    public int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length-1);
        return nums;
    }
    private void quicksort(int[] nums, int start, int end) {
        if (nums == null || nums.length == 0) {
            return;
        }
        // start是有可能大于end的！！
        if (start >= end) {
            return;
        }
        // pivot可以任意选但是它必须放在最后方便partition
        int pivot = nums[end];
        // right是小于等于pivot的segment的右端点，
        // 一开始没有元素大于pivot因此处于start-1位置
        
        // 遍历数组 把小的扔到左边
        int right = start - 1;
        for (int i = start; i < end; i++) {
            if (nums[i] <= pivot) {
                swap(nums, i, ++right);
            } 
        }
        swap(nums, end, ++right);
        // right-1是因为pivot不需要再sort了
        quicksort(nums, start, right-1);
        quicksort(nums, right+1, end);
    }
    private void swap(int[] nums, int i1, int i2) {
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}