排序 三 快速排序

快速排序是一种分治排序算法。快速排序需要先找到一个基准值v和经过初步交换得到的此基准值v在数组中的下标p，经过初步交换的数组在p之前位置的元素<v,在p之后的元素>v.
寻找v和p的过程叫做切分（partition）。然后分别对左半部分和右半部分排序。切分的算法有多种。

一种切分算法
private static <T> int partition(Comparable<T> [] a,int lo,int hi)
{
        
   int i = lo, j = hi+1;  //左右扫面指针
   Comparable<T> v = a[lo];   //切分元素
    while (true) 
    {       //扫描左右，检查扫描是否结束并交换元素
        while(less(a[++i], v)) if (i==hi) break;
        while(less(v, a[--j] )) if(j ==lo)  break;  // 注意数组越界问题
        if(i>= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);    // 将 v = a[j] 放入正确的位置
    return j;    // a[lo...j-1] <= a[j] <= a[j+1...hi]
}

// 最后得出基准值v和p。接下来需要分别排序j-1之前的元素和j+1之后的元素

void sort(Comparable<T> [] a,int lo,int hi) {
    if (hi <= lo) {
        return;
    }
    int j = partition(a, lo, hi);  // 切分 部分交换了元素位置
    sort(a, lo, j-1);                 //将左半部分排序
    sort(a,j+1,hi);                  //将右半部分排序
}

实际情况数组中可能有大量的重复元素，一个元素全部重复的子数组就不需要继续排序了，但是上文的算法还是继续切分成更小的数组进行排序。因此人们想到可以把数组分成三个部分分别对应小于、等于和大于切分元素的数组元素。

三向切分的快速排序

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

a[i] < v ，将a[lt]和a[i]交换，将lt和i加1；
a[i] > v，将a[gt]和a[i]交换，将gt减1；
a[i] = v ，将 i加1