那些可以用快速排序秒殺的經(jīng)典題（一）

今天我們一起來看一下可以用快速排序秒殺的經(jīng)典題，或許這些題目大家已經(jīng)做過，不過可以再來一起復(fù)習(xí)一遍，加深印象。

https://www.jianshu.com/p/356604b8903f

輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]

輸入：nums = [2,0,1]
輸出：[0,1,2]

輸入：nums = [0]
輸出：[0]

輸入：nums = [1]
輸出：[1]

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = 0;
        //這里和三向切分不完全一致
        int i = left;
        int right = len-1;

        while (i <= right) {
             if (nums[i] == 2) {
                 swap(nums,i,right--);
             } else if (nums[i] == 0) {
                 swap(nums,i++,left++);
             } else {
                 i++;
             }
        }     
    }
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

代碼

class Solution {
    public void sortColors(int[] nums) {

        int left = 0;
        int len = nums.length;
        int right = len - 1;
        for (int i = 0; i <= right; ++i) {
            if (nums[i] == 0) {             
                swap(nums,i,left);
                left++;
            }
            if (nums[i] == 2) {
                swap(nums,i,right);
                right--;
                //如果不等于 1 則需要繼續(xù)判斷，所以不移動 i 指針，i--
                if (nums[i] != 1) {
                    i--;
                }
            }
        }

    }
    public void swap (int[] nums,int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}