75. 颜色分类和三路快排

三路快排
从左到右遍历数组一次,维护一个指针lt,使得a[lo...lt-1]中的元素都小于v,一个指针gt使得a[gt+1...hi]都大于v,一个指针i使得a[lt...i-1]中的元素都等于v.
a[i] < v:a[lt]和a[i]交换,i++,lt++
a[i] = v:i++
a[i] > v:a[gt]和a[i]交换,gt--

切分过程

 private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo + 1;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if      (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
        assert isSorted(a, lo, hi);
    }

颜色分类,把只有0,1,2三个元素的数组排序.
这不就是上面的一种特殊情况吗?

    public static void sortColors(int[] nums) {
            //双指针
            int low = 0, high = nums.length - 1;
            int i = 0;
            while (i <= high) {
                if (nums[i] == 0) {
                    swap(nums, low, i);
                    ++low;
                    ++i;
                } else if (nums[i] == 1) {
                    ++i;
                } else if (nums[i] == 2) {
                    swap(nums, high, i);
                    --high;
                }
            }
        }

        private static void swap(int[] nums, int low, int i) {
            int tmp = nums[i];
            nums[i] = nums[low];
            nums[low] = tmp;
        }

参考:1.liuyubobo的玩转算法
2.力扣题解
3.算法四快速排序.