参考自 《算法》第四版

快排

private void sort(Comparable[] a, int lo, int hi) {
    if(lo > hi)
        return;
    
    //切分
    int j = partition(a, lo, hi);
    
    sort(a, lo, j-1);
    sort(a, j+1, hi);
}

//快排的切分，主要排序逻辑
private void partition(Comparable[] a, int lo, int hi) {
    int i = lo, j = hi+1;
    //切分元素
    Comparable 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;
            
        exchange(a, i, j);    
    }
        
    exchange(a, lo, j);
    //完成了 a[lo..j-1] <= a[j] <= a[j+1.. hi]
    return j;
}

private int less(Comparable a, Comparable b) {
    return c.compareTo(b) < 0;
}

private exchange(Comparable[] a, int i, int j) {
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
}

三路快排 适用于数组里有较多重复元素

private void partition(Comparable[] a, int lo, int hi) {
    
    if(lo >= hi)
        return;
        
    int i =  lo+1, j = hi;
    Conparable v = a[lo];
    
    while(j <= j) {
        int cmp = a[i].compareTo(v);
        if(com < 0)
            exchange(a, lo++, i++);
        else if(com > 0)
            exchange(a, i, j--);
        else
            i++;
    }
    
    sort(a, lo, i-1);
    sort(a, j+1, hi);
}