【重点】【三指针】【荷兰国旗问题】【快排】75.颜色分类

题目

法1：快排

必须掌握快排方法！！！

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        quickSort(0, n - 1, nums);
    }

    public void quickSort(int start, int end, int[] nums) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        while (left < right) {
            while (nums[right] > nums[start] && left < right) {
                --right;
            }
            while (nums[left] <= nums[start] && left < right) {
                ++left;
            }
            if (left < right) {
                swap(left, right, nums);
            }
        }
        swap(start, right, nums);

        quickSort(start, left - 1, nums);
        quickSort(left + 1, end, nums);
    }

    public void swap(int left, int right, int[] nums) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

法2：三指针/荷兰国旗问题

思路还是很清晰的，多指针，一头一尾分别用来放置0和2
中间的指针则进行遍历，发现元素0则跟头指针交换元素，并各自加1，发现元素2则跟尾指针交换，尾指针减1

class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1, curInx = 0;
        while (curInx <= right) { // 注意这里需要有"="
            if (nums[curInx] == 0) {
                swap(left, curInx, nums);
                ++left;
                ++curInx;
            } else if (nums[curInx] == 2) {
                swap(right, curInx, nums);
                --right; // 交换过来的这个新的nums[curInx]还要继续进行鉴定
            } else {
                ++curInx;
            }
        }
    }

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