Question

java 关于冒泡排序的优化，下面这种优化的原理是什么？？

方法②：记录每一次元素交换的位置，当元素交换的位置在第0个元素时，则排序结束。

Answer 1

冒泡排序的优化版原理在于如果循环体发生过交换那么它的哨兵肯定是变化过的，反之哨兵还是原来的。而这个哨兵你可以用数组下标为0即首元素作为哨兵也可以，也可以借助其它辅助变量。例如下面的算法冒泡算法优化版是借助了flag作为哨兵:

// 冒泡算法优化版
static void bubbleSort(int ...array){
		int i,j;
		boolean flag=true;
		for(i=0;i<array.length&&flag;i++){
			flag=false;
			for(j=array.length-2;j>=i;j--){ // 由后往前逆推
				if(array[j]>array[j+1]){
					int temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
					flag=true;
				}
			}
		}
		
		for(int item:array){
			 System.out.println(item);
		 }
}