75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

快速排序是原地排序，因此此问题可以采用快速排序解决。

选择left上的元素pivot，设置一个指针index为left+1。
遍历left+1至right的数组，如果遍历的值小于pivot则将nums[i]与nums[index]交换，然后将index向右移动。

因此index左侧的元素均小于pivot，index右侧的元素均大于pivot。
最后将nums[index]与pivot交换，此时pivot左侧元素均小于它，右侧元素均大于它，因此index不需要再动。
然后分别向下递归left至index-1，index+1至right。

class Solution {
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length-1);
    }
    
    private void quickSort(int[] nums, int left, int right){
        if( right - left < 1 ){
            return;
        }
        int pivot = nums[left];
        int index = left+1;
        for(int i = index; i <= right; i++){
            if(nums[i] < pivot){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
        index--;
        
        nums[left] = nums[index];
        nums[index] = pivot;
        
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }
}