冒泡排序优化
1.基础版本
public static void main(String[] args){
int[] arr1= {1,2,6,36,10,7,91,92,93,94};
bubbleSort(arr1);
}
/**
* 冒泡排序初级版本
* @param arr
*/
public static void bubbleSort(int[] arr){
int temp = 0;
for(int i = 0;i < arr.length;i ++){
for(int j = 0; j < arr.length - (i+1);j ++){
if(arr[j]>arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
Arrays.stream(arr).forEach(a->System.out.println(a));
}结果：
1
2
6
7
10
36
91
92
93
94加上具体的日志，看看每一步都做了什么：
public static void bubbleSort1(int[] arr){
int temp = 0;
for(int i = 0; i < arr.length; i++){
System.out.println("============第"+(i)+"轮=============");
for(int j = 0; j < arr.length - (i + 1); j ++){
System.out.println("arr.length-i-1="+(arr.length - i - 1));
System.out.println("第"+j+"和第"+(j+1)+"比");
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
Arrays.stream(arr).forEach(a->System.out.println(a));
}============第0轮=============
arr.length-i-1=9
第0和第1比
arr.length-i-1=9
第1和第2比
arr.length-i-1=9
第2和第3比
arr.length-i-1=9
第3和第4比
arr.length-i-1=9
第4和第5比
arr.length-i-1=9
第5和第6比
arr.length-i-1=9
第6和第7比
arr.length-i-1=9
第7和第8比
arr.length-i-1=9
第8和第9比
============第1轮=============
arr.length-i-1=8
第0和第1比
arr.length-i-1=8
第1和第2比
arr.length-i-1=8
第2和第3比
arr.length-i-1=8
第3和第4比
arr.length-i-1=8
第4和第5比
arr.length-i-1=8
第5和第6比
arr.length-i-1=8
第6和第7比
arr.length-i-1=8
第7和第8比
============第2轮=============
arr.length-i-1=7
第0和第1比
arr.length-i-1=7
第1和第2比
arr.length-i-1=7
第2和第3比
arr.length-i-1=7
第3和第4比
arr.length-i-1=7
第4和第5比
arr.length-i-1=7
第5和第6比
arr.length-i-1=7
第6和第7比
============第3轮=============
arr.length-i-1=6
第0和第1比
arr.length-i-1=6
第1和第2比
arr.length-i-1=6
第2和第3比
arr.length-i-1=6
第3和第4比
arr.length-i-1=6
第4和第5比
arr.length-i-1=6
第5和第6比
============第4轮=============
arr.length-i-1=5
第0和第1比
arr.length-i-1=5
第1和第2比
arr.length-i-1=5
第2和第3比
arr.length-i-1=5
第3和第4比
arr.length-i-1=5
第4和第5比
============第5轮=============
arr.length-i-1=4
第0和第1比
arr.length-i-1=4
第1和第2比
arr.length-i-1=4
第2和第3比
arr.length-i-1=4
第3和第4比
============第6轮=============
arr.length-i-1=3
第0和第1比
arr.length-i-1=3
第1和第2比
arr.length-i-1=3
第2和第3比
============第7轮=============
arr.length-i-1=2
第0和第1比
arr.length-i-1=2
第1和第2比
============第8轮=============
arr.length-i-1=1
第0和第1比
============第9轮=============这个版本，有一个问题：前三个元素，本来就是有序的，但是他们还是走了第7，8，9这三轮。所以，我们可以进行一下优化，如果这一轮没有元素进行交换了，那就停止；我们使用一个标志位，来记录一下：
2.优化版本1
设置一个变量，如果某一轮没有发生元素交换，那说明数组已经有序，就可以停止比较了。
public static void main(String[] args){
int[] arr1= {1,2,6,36,10,7,91,92,93,94};
bubbleSort1(arr1);
}
/**
* 冒泡排序优化1
* @param arr
*/
public static void bubbleSort1(int[] arr){
int temp = 0;
for(int i = 0; i < arr.length; i++){
//每一轮开始，都把标志位设置为true
boolean isSorted = true;
System.out.println("============第"+(i)+"轮=============");
for(int j = 0; j < arr.length - (i + 1); j ++){
System.out.println("arr.length-i-1="+(arr.length - i - 1));
System.out.println("第"+j+"和第"+(j+1)+"比");
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//当这一轮下来，没有元素进行交换式，那就可以停止了
isSorted = false;
}
}
if(isSorted){
break;
}
}
Arrays.stream(arr).forEach(a->System.out.println(a));
}这个版本还是有一个问题：每一轮下来，后面的元素从某个地方开始，其实已经有序了，可是还是在不断的作比较，每一轮下来，右边的有序的元素个数，其实和轮数是相等的，第一轮后，右边有一个有序的，第二轮后，右边有2个有序的，第n轮后，右边有n和有序的。
3.优化版本2
设置一个变量，记录一下每一轮最后一次交换元素的位置，它右边的元素都是有序的了，所以，后面的排序，可以只比较到这一步即可结束。
public static void main(String[] args){
int[] arr1= {1,2,6,36,10,7,91,92,93,94};
bubbleSort1(arr1);
}
/**
* 冒泡排序优化2
* @param arr
*/
public static void bubbleSort1(int[] arr){
int temp = 0;
int lastExchangeIndex = 0;
//无序的边界
int sortBorder = arr.length - 1;
for(int i = 0; i < arr.length; i++){
//每一轮开始，都把标志位设置为true
boolean isSorted = true;
System.out.println("============第"+(i+1)+"轮=============");
//每一轮只比较左边的无序数列
for(int j = 0; j < sortBorder; j ++){
System.out.println("arr.length-i-1="+(arr.length - i - 1));
System.out.println("第"+j+"和第"+(j+1)+"比");
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//当这一轮下来，没有元素进行交换式，那就可以停止了
isSorted = false;
//无需数列的边界更新为最后一次交换元素的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if(isSorted){
break;
}
}
Arrays.stream(arr).forEach(a->System.out.println(a));
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年09月03日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录