public class QuickSort {
    //比較 v 是否小于 w
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }
    //數(shù)組元素交換位置
    private static void swap(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //排序
    public static void sort(Comparable[] a){
        int l = 0;
        int h = a.length - 1;
        sort(a,l,h);
    }
    private static void sort(Comparable[] a,int l,int h){
        if (h <= l)  return;
        //對數(shù)組進行分組(左右兩個數(shù)組)
        // i 表示分組之后基準值的索引
        int i = partition(a, l, h);
        //讓左邊的數(shù)組有序
        sort(a,l,i - 1);
        //讓有邊的數(shù)組有序
        sort(a,i + 1,h);
    }
    public static int partition(Comparable[] a,int l,int h){
        //確定基準值
        Comparable key = a[l];
        //定義兩個指針
        int left = l;
        int right = h + 1;
        //切分
        while (true){
            //從右向左掃描，移動right指針找一個比基準值小的元素，找到就停止
            while (less(key,a[--right])){
                if (right == l)
                    break;
            }
            //從左向右掃描，移動left指針找一個比基準值大的元素，找到就停止
            while (less(a[++left],key)){
                if (left == h)
                    break;
            }
            if (left>=right){
                break;
            }else {
                swap(a,left,right);
            }
        }
        //交換基準值
        swap(a,l,right);
        return right;
    }
}

public class QuickSortTest {
    public static void main(String[] args) {
        Integer[] arr = {3,1,2,4,9,6};
        QuickSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
//排序前：{3,1,2,4,9,6}
//排序后：{1,2,3,4,6,9}