testpaixu.java

DataStructure 我觉得还不错~ 共享给大家~ 有空看看~

package com.itjob.data;
import static java.lang.Math.*;

import java.util.Calendar;
import java.util.Date;
import java.util.GregorianCalendar;

public class TestPaiXu {

	/**
	 * @param args
	 */
	
	static int[] datas ;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		datas = new int[100000];
		for (int i = 0; i < datas.length ; i++){
			datas[i] = (int)(random() * 10000);
		}
		
		/*for (int i = 0; i < datas.length ; i++){
			System.out.print(datas[i] + "  ");
		}
		System.out.println();
		
		shell();
		
		for (int i = 0; i < datas.length ; i++){
			System.out.print(datas[i] + "  ");
		}
		*/
		System.out.println();
		GregorianCalendar gc = new GregorianCalendar();
		System.out.println(gc.get(Calendar.MINUTE) + ":" + gc.get(Calendar.SECOND) + ":" + gc.get(Calendar.MILLISECOND));
		//chaRu();
		//xuanZhe();
		//maoPao();
		shell();
		//quick();
		gc = new GregorianCalendar();
		System.out.println(gc.get(Calendar.MINUTE) + ":" + gc.get(Calendar.SECOND) + ":" + gc.get(Calendar.MILLISECOND));
		
		//xuanZhe();
		//chaRu();
		//quick();
		/*
		for (int i = 0; i < datas.length ; i++){
			System.out.print(datas[i] + "  ");
		}
		*/
	}
	
	public static void xuanZhe(){
		for (int i = 0; i < datas.length - 1; i++){
			int temp = datas[i];
			int rear = i;
			for (int j = i ; j < datas.length ; j++){
				if (datas[j] < temp){
					temp = datas[j];
					rear = j;
				}
			}	
			change(i,rear);
		}
	}
	
	public static void chaRu(){
		int temp = 0;
		for (int i = 1; i < datas.length; i++){
			temp = datas[i];
			int j = i - 1;
			for ( ; j >= 0; j--){
				if (datas[j] < temp){
					datas[j + 1] = datas[j];
				}else{
					break;
				}
			}		
			datas[j + 1] = temp;
		}
	}
	
	
	public static void shell(){
		int size = datas.length;
		int step = 1;
		while(step < size/3){
			step = step * 3 + 1;  // 1 4 13 
		}
		int temp = 0;
		while (step > 0){
			for (int i = step; i < datas.length; i = i + step){
				temp = datas[i];
				int j = i - step;
				for ( ; j >= 0 ; j = j - step){
					if (datas[j] < temp){
						datas[j + step] = datas[j];
					}else{
						break;
					}
				}		
				datas[j + step] = temp;
			}
			
			step = (step - 1)/3;
		}
		
	}
	
	
	public static void maoPao(){
		for (int i = datas.length - 1;i > 0; i--){
			for (int j = 0; j < i; j++){
				if (datas[j] < datas[j + 1]){
					change(j,j+1);
				}
			}
		}
	}
	
	private static void change(int p,int n){
		int temp = 0;
		temp = datas[p];
		datas[p] = datas[n];
		datas[n] = temp;
	}
	
	
	public static void quick(){
		digui(0,datas.length - 1);
	}
	
	public static void digui(int left,int right){
		
		if (left >= right){
			return;
		}else{
			int mxiabiao = pai(left,right);
			digui(left,mxiabiao - 1);
			digui(mxiabiao + 1,right);
		}
	}
	
	public static int  pai(int left,int right){
		int oldleft = left;
		int oldright = right;
		int middle = datas[right];
		while(true){
			while(left < oldright && datas[left] <= middle) left++;
			while(right > oldleft && datas[right] >= middle) right--;
			
			if (left < right){
				change(left,right);
			}else{
				change(left,oldright);
				break;
			}
		}
		
		return left;
	}
	
	

}