冒泡轮数cycle和每轮比较次数compare

数组中从第一个元素开始，依次和后一个元素比较大小，如果前比后大，则交换元素位置，即大的向上冒泡。

每轮比较，都会确定一个最大值，所以至多比较arr.length - 1 轮

比如[3,2,1]，第一轮确定最大值3，[2,1,3]

                     第二轮确定最大值2，[1,2,3]

                     不需要比较第三轮，因为一共就三个数，已经确定了两个最大值了，剩下的就是最小值

由于第一个元素不需要和自己比，且每轮比较都会确定一个最大值，所以每轮不需要和确定的最大值比较，所以每轮至多比较arr.length - 1 - 轮次值（第一轮确定1个最大值，第二轮确定2个最大值） 次。

比如[3,2,1]，第一轮冒泡比较2次，[2,1,3]

                     第二轮冒泡只需要比较1次，不需要和3再次比较

import java.util.*;

public class BasicBubbleSort{
	public static void main(String[] args){
		int[] arr = new int[]{0,1,2,7,3,6,5,4,8,9};
		System.out.println("原数组为：\t"+Arrays.toString(arr));
        sort(arr);
	}
	
	public static void sort(int[] arr){
		// 冒泡轮数
		int cycle = 0;
		// 总比较次数
		int compare = 0;
		// 总交换次数
		int swap = 0;
		
		for(int i = 0; i < arr.length - 1; i++) {
			cycle++;
			for(int j = 0; j < arr.length - 1 - i; j++) {
				compare++;
				if (arr[j] > arr[j+1]) {
					swap++;
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
			System.out.println("第" + cycle + "轮冒泡后数组为:" + Arrays.toString(arr));
		}
		
		System.out.println("冒泡轮数:" + cycle + "\n总比较次数:" + compare + "\n总交换次数:" + swap);
		System.out.println("冒泡排序后数组为：" + Arrays.toString(arr));
	}
}

冒泡优化-有序区

上面每轮冒泡的比较次数为 arr.length - 1 - i ，其中 i 代表的就是冒泡轮数

即：每轮比较后都会确定一个的最大值，比如第一轮确定1个最大值，第二轮确定2个最大值

这些“最大值”的位置就是排序完成后的位置，即 (arr.length - 1 - i) ~ (arr.length - 1) 索引的元素就是有序区。

但是有一种情况，如数组

[6,5,4,3,2,1,7,8,9] 

第一轮i=0冒泡后

[5,4,3,2,1,6,7,8,9] 

按照上面有序区界定方法 (arr.length - 1 - i) ~ (arr.length - 1)，即 只有9是有序区

但是可以发现其实6,7,8,9都是有序区，其界定方法就是最后一次交换位置的地方

import java.util.*;

public class BasicBubbleSort{
	public static void main(String[] args){
		int[] arr = new int[]{0,1,2,7,3,6,5,4,8,9};
		System.out.println("原数组为：\t"+Arrays.toString(arr));
        sort(arr);
	}
	
	public static void sort(int[] arr){
		// 冒泡轮数
		int cycle = 0;
		// 总比较次数
		int compare = 0;
		// 总交换次数
		int swap = 0;
		
		int borderIndex = arr.length - 1;
		int lastSwapIndex = 0;
		
		for(int i = 0; i < arr.length - 1; i++) {
			cycle++;
			for(int j = 0; j < borderIndex; j++) {
				compare++;
				if (arr[j] > arr[j+1]) {
					swap++;
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
					lastSwapIndex = j;
				}
			}
			borderIndex = lastSwapIndex;
			System.out.println("第" + cycle + "轮冒泡后数组为:" + Arrays.toString(arr));
		}
		
		System.out.println("冒泡轮数:" + cycle + "\n总比较次数:" + compare + "\n总交换次数:" + swap);
		System.out.println("冒泡排序后数组为：" + Arrays.toString(arr));
	}
}

冒泡优化-整体有序识别

前面排序结果发现，在整体有序后，由于冒泡外层for循环轮数还没有结束，所以就算整体有序后，还是在无意义循环冒泡。

所以当整体有序时，就可以终止冒泡。

整体有序时刻其实就是一轮冒泡过程中没有发生交换元素的情况。

import java.util.*;

public class BasicBubbleSort{
	public static void main(String[] args){
		int[] arr = new int[]{0,1,2,7,3,6,5,4,8,9};
		System.out.println("原数组为：\t"+Arrays.toString(arr));
        sort(arr);
	}
	
	public static void sort(int[] arr){
		// 冒泡轮数
		int cycle = 0;
		// 总比较次数
		int compare = 0;
		// 总交换次数
		int swap = 0;
		
		int borderIndex = arr.length - 1;
		int lastSwapIndex = 0;
		
		for(int i = 0; i < arr.length - 1; i++) {
			cycle++;
			boolean finished = true;
			for(int j = 0; j < borderIndex; j++) {
				compare++;
				if (arr[j] > arr[j+1]) {
					swap++;
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
					lastSwapIndex = j;
					finished = false;
				}
			}
			
			if(finished){
				break;
			}
			
			borderIndex = lastSwapIndex;
			
			System.out.println("第" + cycle + "轮冒泡后数组为:" + Arrays.toString(arr));
		}
		
		System.out.println("冒泡轮数:" + cycle + "\n总比较次数:" + compare + "\n总交换次数:" + swap);
		System.out.println("冒泡排序后数组为：" + Arrays.toString(arr));
	}
}

冒泡优化-双向冒泡，鸡尾酒排序，无序区

上面的冒泡是单向冒泡，即大的元素向上冒泡。单向冒泡可以界定出有序区，即最后一次交换元素的位置到arr.length-1索引位置。

但是也有这样一种情况

[0,1,2,7,3,6,5,4,8,9]

其中0，1，2是有序的，8,9是有序的，所以单向冒泡的有序区就不太好支持了，我们可以使用无序区概念，即7,3,6,5,4。我们在一次冒泡过程中，先从小到大正向冒泡，再从大到小反向冒泡。就可以双倍速度缩小无序区，增大双边有序区。

import java.util.*;

public class BasicBubbleSort{
	public static void main(String[] args){
		int[] arr = new int[]{0,1,2,7,3,6,5,4,8,9};
		System.out.println("原数组为：\t"+Arrays.toString(arr));
        sort(arr);
	}
	
	public static void sort(int[] arr){
		// 冒泡轮数
		int cycle = 0;
		// 总比较次数
		int compare = 0;
		// 总交换次数
		int swap = 0;
		
		int borderMinIndex = 0;
		int borderMaxIndex = arr.length - 1;
		int lastSwapIndex = 0;
		
		for(int i = 0; i < arr.length/2; i++) {
			cycle++;
			
			// 正向冒泡
			boolean finished = true;
			for(int j = borderMinIndex; j < borderMaxIndex; j++) {
				compare++;
				if (arr[j] > arr[j+1]) {
					swap++;
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
					lastSwapIndex = j;
					finished = false;
				}
			}
			
			if(finished || (borderMaxIndex == borderMinIndex)){
				System.out.println("第" + cycle + "轮冒泡后数组为:" + Arrays.toString(arr));
				break;
			}
			
			borderMaxIndex = lastSwapIndex;
			
			// 反向冒泡
			for(int k = borderMaxIndex; k > borderMinIndex; k--) {
				compare++;
				if (arr[k] < arr[k-1]) {
					swap++;
					int tmp = arr[k];
					arr[k] = arr[k-1];
					arr[k-1] = tmp;
					lastSwapIndex = k;
					finished = false;
				}
			}
			
			if(finished || (borderMaxIndex == borderMinIndex)){
				System.out.println("第" + cycle + "轮冒泡后数组为:" + Arrays.toString(arr));
				break;
			}
			
			borderMinIndex = lastSwapIndex;
			
			System.out.println("第" + cycle + "轮冒泡后数组为:" + Arrays.toString(arr));
		}
		
		System.out.println("冒泡轮数:" + cycle + "\n总比较次数:" + compare + "\n总交换次数:" + swap);
		System.out.println("冒泡排序后数组为：" + Arrays.toString(arr));
	}
}