java快速排序

//快速排序思想:选择数组最后一个数(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;
	}
}

java快速排序,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。