public class Test2 {
	static List<Integer> list = new ArrayList<Integer>();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		list.add(1);
		list.add(536);
		list.add(599);
		list.add(36);
		list.add(15);
		list.add(88);
		list.add(65);
		list.add(45);
		list.add(52);
		list.add(55);
//		test();
		//快速排序
		System.out.println("原集合:"+list);
		queckSort(0, list.size()-1);
		System.out.println("排序后:"+list);
		//插入排序
//		System.out.println("原集合:"+list);
//		insertSort();
//		System.out.println("排序后:"+list);	
		//选择排序
//		System.out.println("原集合:"+list);
//		selectSort();
//		System.out.println("排序后:"+list);	
//		//冒泡排序
//		System.out.println("原集合:"+list);
//		maoPaoSort();
//		System.out.println("排序后:"+list);	
	}
	/**
	 * 快速排序
	 * @param left
	 * @param right
	 */
	public static void queckSort(int left,int right){
		int temp;
		if(left > right)
			return ;
		temp = list.get(left);
		int i = left;
		int j = right;
		while(i!=j)
		{
			while((list.get(j)<=temp)&&i<j)
				j--;
			while((list.get(i)>=temp)&&i<j)
				i++;
			if(i<j)
			{
				int t = list.get(j);
				list.set(j, list.get(i));
				list.set(i, t);
			}
			System.out.println(list);
		}
		list.set(left, list.get(i));
		list.set(i, temp);
		queckSort(left, i-1);
		queckSort(i+1, right);
		
	}
	/**
	 * 插入排序
	 * 3 1 2 4 5 
	 */
	public static void insertSort(){
		int i,j,temp;
		for(i = 1;i<list.size();i++)
		{   
			temp = list.get(i);
			for(j=i-1;j>=0&&temp<list.get(j);j--)
				{
				list.set(j+1, list.get(j));
				System.out.println(list);
				}
				
			list.set(j+1, temp);
			
		}
	}
	/**
	 * 选择排序、
	 * 
	 * */
	public static void selectSort(){
		int t;
		for(int i = 0;i<list.size()-1;i++)
			for(int j = i+1;j<list.size();j++)
			{	if(list.get(i)>list.get(j)){
					t = list.get(i);
					list.set(i, list.get(j));
					list.set(j, t);
				}
				System.out.println(list);
			}
		}
	/**
	 * 冒泡排序
	 */
	public static void maoPaoSort(){
		int t;
		for(int i = 0 ; i<list.size()-1;i++)
			for(int j = 0;j<list.size()-1-i;j++)
				if(list.get(j)<list.get(j+1))
				{
					t = list.get(j+1);
					list.set((j+1), list.get(j));
					list.set(j, t);	
				}
	}
}