/**
 * 功能：排序算法的演示
 */
package com.text;

import java.util.Calendar;

public class Text2 {

	public static void main(String[] args) {
		
		int len=100000;
		
		int a[]=new int[len];
		
		for (int i = 0; i < a.length; i++) {
			int t=(int)Math.random()*10000;
			
			a[i]=t;
		}
		
//		Quick quick=new Quick();
		Insert insert=new Insert();
		//在排序前打印系统时间
		Calendar cal=Calendar.getInstance();
		System.out.println("排序前："+cal.getTime());
		insert.insertSort(a);
//		quick.quickSort(0, a.length-1,a);
		cal=Calendar.getInstance();
		System.out.println("排序后："+cal.getTime());
		
		/*int a[]={1,5,2,15,6,-2,11,12,100,56,79,21,1000,566};
		Quick quick=new Quick();
		quick.quickSort(0, a.length-1,a);
		for (int i = 0; i < a.length; i++) {
			System.out.print("  "+a[i]);
		}*/

	}

}


//选择排序
class Insert{
	int temp;
	public void insertSort(int a[]){
		for (int i = 0; i < a.length-1; i++) {
			int min=a[i];
			//记录最小值的下标
			int minIndex=i;
			for (int j = i+1; j < a.length; j++) {
				if (min>a[j]) {
					//修改最小值
					min=a[j];
					minIndex=j;
				}
			}
			temp=a[i];
			a[i]=a[minIndex];
			a[minIndex]=temp;
		}
	}
		
}

//快速排序
class Quick{
	public void quickSort(int left,int right,int a[]){
		int l=left;
		int r=right;
		int pivot = a[(left+right)/2];
		int temp = 0;
		
		while(l<r){
			
			while(a[l]<pivot) 
				l++;
			while(a[r]<pivot)
				r--;
			
			if (l>=r)
				break;
			
			temp=a[l];
			a[l]=a[r];
			a[r]=temp;
			
			if(a[l]==pivot)
				--r;
			if(a[r]==pivot)
				++l;
		}
		
		if(l==r){
			l++;
			r--;
		}
		
		if(left<r) quickSort(left, r,a);
		if(r>right) quickSort(l, right,a);
			
			
	}
}