//快速排序思想：选择数组最后一个数（key)，比它小的排他前面 ( key放中间 )  比它大的排后面， 然后递归  终止条件（数组只有一个数）public class Sort<T extends Comparable<T>> {    //能排序的都是能比较的，所以必须继承java.lang.Comparable

	public void quick(T[] array){
		sort(array,0,array.length-1);
	}
	
	private void sort(T[] array ,int left,int right){  
		if(left<right){
			
		int p=partition(array,left,right);  
		sort(array,left,p-1);
		sort(array,p+1,right);
		
		}
	}
	private int partition(T[] array,int left,int right){
	
		int i=left-1;
		for(int j=left;j<right;j++)
		{
			if(array[j].compareTo(array[right])<=0)    
			{
				i++;                   // 理解 int i=left-1 和 return i+1; 细节细节！！！需要自己体会
				swap(array,i,j);
			}
			
		}
		swap(array,i+1,right);   //  把key 插入
		return i+1;
	}
	private void swap(T[] array, int i,int j){
		T t=array[i];
		array[i]=array[j];
		array[j]=t;
	}
}