public class Quick {
    /*
  比较v元素是否小于w元素
*/
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    /*
   数组元素i和j交换位置
    */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    /*
    对组内元素进行排序
     */
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    //对数组a中从索引lo到索引hi之间的元素进行排序
    private static void sort(Comparable[] a, int lo, int hi) {
        if(lo>=hi){
            return;
        }
        //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；
        int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引

        //让左子组有序
        sort(a,lo,partition-1);

        //让右子组有序
        sort(a,partition+1,hi);
    }
    private static int partition(Comparable[] a, int lo, int hi) {
        int key = lo;
        int begin = lo;
        int end = hi+1;
        while(true){
            while(less(a[key],a[--end])) {              //如果右边的元素小于key
                if (end == lo) {
                    break;
                }
            }
            while(less(a[++begin],a[key])){          //从左边开始轮
                if(begin==hi){
                    break;
                }
            }
            //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (begin>=end){
                break;
            }else{
                exch(a,begin,end);
            }
        }
        exch(a,key,end);
        return end;
    }