package sort;

/**
 * 三向切分的快速排序 ：
 * 对于每次切分：从数组的左边到右边遍历一次，维护三个指针，
 * lt指针使得元素（arr[0]-arr[lt-1]）的值均小于切分元素；
 * gt指针使得元素（arr[gt+1]-arr[N-1]）的值均大于切分元素；
 * i指针使得元素（arr[lt]-arr[i-1]）的值均等于切分元素，
 * （arr[i]-arr[gt]）的元素还没被扫描，切分算法执行到i>gt为止。
 * 每次切分之后，位于gt指针和lt指针之间的元素的位置都已经被排定，
 * 不需要再去处理了。之后将（lo,lt-1）,（gt+1,hi）分别作为处理左
 * 子数组和右子数组的递归函数的参数传入，递归结束，整个算法也就结束。
 */
public class Quick3way {
    public void sort(Comparable[] a, int lo, int hi) {
        int lt = lo, i = lo + 1, gt = hi;
        while (i >= gt) {
            if (a[i].compareTo(a[lo]) < 0) {
                exch(a, i++, lt++);
            } else if (a[i].compareTo(a[lo]) > 0) {
                exch(a, i, gt--);
            } else {
                i++;
            }
        }
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }
    private void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}