package com.jackie.bubbleSort;

import java.util.Arrays;

/**
 * 用冒泡排序方法实现对 9 8 7 6 5 的升序排序
 * 思路分析：
 * 	第一趟：从以上数据中找出最大的数字9
 * 		第一次：8 9 7 6 5 	8和9交换
 * 		第二次：8 7 9 6 5		7和9交换
 * 		第三次：8 7 6 9 5 	6和9交换
 * 		第四次：8 7 6 5 9		5和9交换
 * 	第二趟：从以上数据中找出数字8
 * 		第一次：7 8 6 5 9 	7和8交换
 * 		第二次：7 6 8 5 9		6和8交换
 * 		第三次：7 6 5 8 9 	5和8交换
 * 		第四次：7 6 5 8 9		8和9交换，不用交换位置
 * 	第三趟：从以上数据中找出数字7
 * 		第一次：6 7 5 8 9	 	6和7交换
 * 		第二次：6 5 7 8 9		5和7交换
 * 		第三次：6 5 7 8 9 	7和8交换，不用交换位置
 * 		第四次：6 5 7 8 9		7和9交换，不用交换位置
 * 	第四趟：从以上数据中找出数字6
 * 		第一次：5 6 7 8 9	 	5和6交换
 * 		第二次：5 6 7 8 9		6和7交换，不用交换位置
 * 		第三次：5 6 7 8 9	 	6和8交换，不用交换位置
 * 		第四次：5 6 7 8 9		6和9交换，不用交换位置
 * 
 * 通过对以上的分析以及代码执行结果可发现，该版本仍存在可优化的地方，
 * 如第一趟8和9已经比较过了，但是第二趟又进行了一次比较，因此可简化如下形式：
 * 经过简化后发现执行次数少了很多
 * 	第一趟：从以上数据中找出最大的数字9
 * 		第一次：8 9 7 6 5 	8和9交换
 * 		第二次：8 7 9 6 5		7和9交换
 * 		第三次：8 7 6 9 5 	6和9交换
 * 		第四次：8 7 6 5 9		5和9交换
 * 	第二趟：从以上数据中找出数字8
 * 		第一次：7 8 6 5 9 	7和8交换
 * 		第二次：7 6 8 5 9		6和8交换
 * 		第三次：7 6 5 8 9 	5和8交换
 * 	第三趟：从以上数据中找出数字7
 * 		第一次：6 7 5 8 9	 	6和7交换
 * 		第二次：6 5 7 8 9		5和7交换
 * 	第四趟：从以上数据中找出数字6
 * 		第一次：5 6 7 8 9	 	5和6交换
 * 
 * 优化最终版本：假设数据有序，后者经过某趟后有序，减少趟数
 * 如： 8 1 2 3 4
 * 第一趟：1 2 3 4 8
 * 第二趟：1 2 3 4 8 没有经过任何交换，停止
 * @author liutao
 * @date 2017年12月4日 下午4:10:31
 */
public class BubbleSort3 {
	public static void main(String[] args) {
		int[] arr = {9,8,7,6,5};
		arr = new int[]{9,1,2,3,4};
		arr = new int[]{8,9,1,2,3,4};
		arr = new int[]{1,2,3,9,4};
		sort(arr);
		//sortFinal(arr);
	}
	public static void sort(int[] arr){
		int temp;
		int len = arr.length;
		boolean sorted = true;
		//执行趟数
		for(int j = 0;j < len - 1; j ++){
			sorted = true;//假定有序
			//执行次数
			for(int i = 0;i < len - 1 - j; i ++){
				System.out.print("第" + (j + 1) + "趟，");
				System.out.print("第" + (i + 1) + "次：");
				if(arr[i] > arr[i + 1]){
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					sorted = false;//假定失败
				}
				System.out.println(Arrays.toString(arr));
			}
			if(sorted){
				break;
			}
		}
	}
}