快速排序

  package com.snail.basic;

public class Quick
{

    public static void sort(Comparable[] a){
        // 将数组打乱 StdRandom.shuffle(a)
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable[] a, int low, int high){
        if(high<=low) return;
        int j = partnation(a,low,high);
        sort(a,low,j-1);
        sort(a,j+1,high);
    }
    public static int partnation(Comparable[] a,int low,int high){
        int i = low;
        int j = high;
        Comparable v = a[low];

        while (true){
            // 找出比他小的
            while (less(a[++i],v)){
                if(i == high) break;
            }
            // 找出比他大的
            while (less(v,a[--j])){
                if(j == low) break;
            }
            if(i>=j) break;
            exch(a,i,j);
        }
        // 请注意这个步骤
        exch(a,low,j);
        return j;
    }
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[j]=a[i];
        a[i]=t;
    }

}