快速排序

快速排序

代码样例

public class QuickSort {
    public static void sort(Comparable []a){
        Comparable []s = a.clone();
        quickSort(s, 0, a.length-1);
    }
    private static void quickSort(Comparable []a, int lo, int hi){
        if(hi <= lo){
            return;
        }
        int j = partition(a, lo, hi);
        quickSort(a, lo,j-1);
        quickSort(a, j+1, hi);
    }
    private static int partition(Comparable [] a, int lo, int hi){
        int i  = lo;
        int 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;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
    private static Boolean less(Comparable a, Comparable b){
        return a.compareTo(b) < 0 ? true:false ;
    }
    private static void exch(Comparable []a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
}