Feng's Blog

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class SortPractice1 {
	
	public static int[] createArray(int num){
		int[] buf = new int[num];
		Random r = new Random();
		for(int i=0;i<num;i++){
			buf[i] = r.nextInt();
		}
		return buf;
	}

	/**
	 * Sort Practice one
	 * @param args
	 */
	public static void main(String[] args) {
		//-------100000
		//select 34859
		//bubble 34906
		//insert 7953
		//quick 563
		
		//----10000
		//select 344
		//bubble 344
		//insert 78
		//quick 62
		
		//----1000
		//select 0
		//bubble 0
		//insert 0
		//quick 31
		
		long start;
		long end;
//		int[] ary = {10,17,8,2,50,11,4,100,55,27};
		int[] copy = createArray(100);
		int[] ary = null;
		
		System.out.println("快速排序");
		ary = Arrays.copyOf(copy,copy.length);
		start = System.currentTimeMillis();
		ary = quick(ary); //排序
		end = System.currentTimeMillis();
		System.out.println(end-start);
		check(ary);
		
		System.out.println("冒泡排序");
		ary = Arrays.copyOf(copy, copy.length);
		start = System.currentTimeMillis();
		ary = bubble(ary); //排序
		end = System.currentTimeMillis();
		System.out.println(end-start);
		check(ary);
		
		System.out.println("选择排序");
		ary = Arrays.copyOf(copy, copy.length);
		start = System.currentTimeMillis();
		ary = select(ary); //排序
		end = System.currentTimeMillis();
		System.out.println(end-start);
		check(ary);
		
		System.out.println("插入排序");
		ary = Arrays.copyOf(copy, copy.length);
		start = System.currentTimeMillis();
		ary = insert(ary); //排序
		end = System.currentTimeMillis();
		System.out.println(end-start);
		check(ary);
	}
	
	public static void check(int[] ary) {
		for(int i=0;i<ary.length-1;i++){
			if(ary[i]>ary[i+1]){
				System.out.println("错误的序列！");
				return;
			}
		}
		System.out.println("正确的序列");
	}

	public static int[] bubble(int[] n){
		int times = 0;
		int moves = 0;
		
		for(int i=0; i<n.length-1; i++){
			for(int j=0; j<n.length-1-i; j++){
				if(n[j]>n[j+1]){ 
					int temp = n[j];
					n[j] = n[j+1];
					n[j+1] = temp;
					moves++;
				}
				times++;
			}
		}
		System.out.println("循环次数:"+times+",移值次数:"+moves);
		return n;
	}
	
	public static int[] quick(int[] n){
		int times = 0;
		int moves = 0;
		ArrayList<String> list = new ArrayList<String>();
		list.add(0+","+(n.length-1));
		while(list.size()>0){
			String[] params = list.get(0).split(",");
			list.remove(0);
			int start = Integer.parseInt(params[0]);
			int end = Integer.parseInt(params[1]);
			int key = start;
			int i = key+1;
			int j = end;
			boolean left = true;
			while(i<=j){
				times++;
				if(left){//从后往前搜索
					if(n[key]>n[j]){
						moves++;
						int temp = n[j];
						n[j] = n[key];
						n[key] = temp;
						key = j;
						left = false;
					}
					j--;
				}else{
					if(n[key]<n[i]){
						moves++;
						int temp = n[i];
						n[i] = n[key];
						n[key] = temp;
						key = i;
						left = true;
					}
					i++;
				}
			}
			if(key>start+1){ //1.start==key;2.start,key;3.start,...,key 第三种情况才需要进行再次排序
				list.add(start+","+(key-1));
			}
			if(end>key+1){
				list.add(key+1+","+end);
			}
		}
		System.out.println("循环次数:"+times+",移值次数:"+moves);
		return n;
	}

	public static int[] insert(int[] n){
		int outtimes = 0;
		int intimes = 0;
		for(int i=1,j=0; i<n.length; i++){
			int temp = n[i];
			for(j=i-1; j>=0&&temp<n[j]; j--){
					intimes++;
					n[j+1] = n[j];
			}
			n[j+1] = temp;
			outtimes++;
		}
		System.out.println("内循环次数:"+intimes+",外循环次数:"+outtimes);
		return n;
	}
	
	public static int[] select(int[] n){
		int times = 0;
		int moves = 0;
		for(int i=0; i<n.length-1; i++){
			for(int j=i+1; j<n.length; j++){
				if(n[i]>n[j]){
					int temp = n[i];
					n[i] = n[j];
					n[j] = temp;
					moves++;
				}
				times++;
			}
		}
		System.out.println("循环次数:"+times+",移值次数:"+moves);
		return n;
	}
}

参考资料：

http://www.cnblogs.com/herbert/archive/2011/01/20/1940392.html