five.java

两个贪心实例

     
       
      
 public class five{
	
	private static int myArray[]={3,5,7,2,4,7,21,1};
private static  void qSort(int p,int r){
	
	if(p<r){
		int q=partition(p,r);
		qSort(p,q-1);
		//对左半段排序
		qSort(q+1,r);
		//对右半段排序
		
	}
}
private  static int partition(int p,int r){
	int i=p,j=r+1;
	int x=myArray[p],t;
        //将<=x的元素交换到右边
        //将>=x的元素交换到左边
	while(true){
		while(myArray[++i]>x);
		while(myArray[--j]<x);
		if(i>=j) break;
		t=myArray[i];
		myArray[i]=myArray[j];
		myArray[j]=t;
	}
	myArray[p]=myArray[j];
	myArray[j]=x;
return j;
}


public  static void main(String[] args ){
	int n=myArray.length;
	
	for(int i=0;i<n-1;i++){
		qSort(0,7);
		System.out.println(myArray[n-2-i]+"与"+myArray[n-1-i]+"合并为:");
		myArray[n-2-i]=myArray[n-1-i]+myArray[n-2-i];
		myArray[n-1-i]=0;
		for(int j=0;j<n-i-1;j++){
			System.out.print(myArray[j]+" ");
		}
		System.out.println();
	}
		

}
}