读懂三向快速排序

package com.snail.basic;

public class Quick3Way {
    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        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);
    }
    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[j] = a[i];
        a[i] = t;
    }

}