源代码：https://gitee.com/AgentXiao/DataStructAndAlgorithm
一、排序算法的基础版本
/**
* @ClassName Bubble01
* @Description 冒泡排序基础版
* @Author xwd
* @Date 2018/10/19 14:58
*/
public class Bubble01 {
public static void main(String[] args) {
int[] arr = {6,5,4,3,7,8,9};
BubbleSort(arr);
}
public static void BubbleSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
System.out.println("第"+(i+1)+"次");
for(int j=0;j<arr.length-1-i;j++){
System.out.print("第"+(j+1)+"躺:");
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
System.out.println(Arrays.toString(arr));
}
}
}
}
控制台信息：
第1次
第1躺:[5, 6, 4, 3, 7, 8, 9]
第2躺:[5, 4, 6, 3, 7, 8, 9]
第3躺:[5, 4, 3, 6, 7, 8, 9]
第4躺:[5, 4, 3, 6, 7, 8, 9]
第5躺:[5, 4, 3, 6, 7, 8, 9]
第6躺:[5, 4, 3, 6, 7, 8, 9]
第2次
第1躺:[4, 5, 3, 6, 7, 8, 9]
第2躺:[4, 3, 5, 6, 7, 8, 9]
第3躺:[4, 3, 5, 6, 7, 8, 9]
第4躺:[4, 3, 5, 6, 7, 8, 9]
第5躺:[4, 3, 5, 6, 7, 8, 9]
第3次
第1躺:[3, 4, 5, 6, 7, 8, 9] //到这里就已经排好序了，下面的次数都属多余的
第2躺:[3, 4, 5, 6, 7, 8, 9]
第3躺:[3, 4, 5, 6, 7, 8, 9]
第4躺:[3, 4, 5, 6, 7, 8, 9]
第4次
第1躺:[3, 4, 5, 6, 7, 8, 9]
第2躺:[3, 4, 5, 6, 7, 8, 9]
第3躺:[3, 4, 5, 6, 7, 8, 9]
第5次
第1躺:[3, 4, 5, 6, 7, 8, 9]
第2躺:[3, 4, 5, 6, 7, 8, 9]
第6次
第1躺:[3, 4, 5, 6, 7, 8, 9]
二、优化版本
/**
* @ClassName Bubble01
* @Description 冒泡排序优化版：一旦有序，不再进行下一趟
* @Author xwd
* @Date 2018/10/19 14:58
*/
public class Bubble02 {
public static void main(String[] args) {
int[] arr = {6,5,4,3,7,8,9};
BubbleSort(arr);
}
public static void BubbleSort(int[] arr){
boolean isDone = true;//是否完成排序标记
for(int i=0;i<arr.length-1;i++){
System.out.println("第"+(i+1)+"次");
isDone = true;//默认这一次不需要进行交换
for(int j=0;j<arr.length-1-i;j++){
System.out.print("第"+(j+1)+"躺:");
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
isDone = false;//假设错误，这一次还是进行了交换
}
System.out.println(Arrays.toString(arr));
}
if(isDone){ //如果这一次没有，说明已经有序了，跳出循环
break;
}
}
}
}
控制台信息：很明显去掉了下面的两次循环
第1次
第1躺:[5, 6, 4, 3, 7, 8, 9]
第2躺:[5, 4, 6, 3, 7, 8, 9]
第3躺:[5, 4, 3, 6, 7, 8, 9]
第4躺:[5, 4, 3, 6, 7, 8, 9]
第5躺:[5, 4, 3, 6, 7, 8, 9]
第6躺:[5, 4, 3, 6, 7, 8, 9]
第2次
第1躺:[4, 5, 3, 6, 7, 8, 9]
第2躺:[4, 3, 5, 6, 7, 8, 9]
第3躺:[4, 3, 5, 6, 7, 8, 9]
第4躺:[4, 3, 5, 6, 7, 8, 9]
第5躺:[4, 3, 5, 6, 7, 8, 9]
第3次
第1躺:[3, 4, 5, 6, 7, 8, 9]
第2躺:[3, 4, 5, 6, 7, 8, 9]
第3躺:[3, 4, 5, 6, 7, 8, 9]
第4躺:[3, 4, 5, 6, 7, 8, 9]
第4次
第1躺:[3, 4, 5, 6, 7, 8, 9]
第2躺:[3, 4, 5, 6, 7, 8, 9]
第3躺:[3, 4, 5, 6, 7, 8, 9]
但是还有问题：第4次第1躺就完成了排序，剩下的两次都是多余的。
三、最终版本
/**
* @ClassName Bubble01
* @Description 冒泡排序最终版：一旦有序，立刻停止排序
* @Author xwd
* @Date 2018/10/19 14:58
*/
public class Bubble03 {
public static void main(String[] args) {
int[] arr = {6,5,4,3,7,8,9};
BubbleSort(arr);
}
public static void BubbleSort(int[] arr){
boolean isDone = true;
int lastExchangeIndex = 0;//最后一次比较的位置
int sortBorder = arr.length - 1;//无序书列的边界，每次比较只需要比较到这个位置
for(int i=0;i<arr.length-1;i++){
System.out.println("第"+(i+1)+"次");
isDone = true;
for(int j=0;j<sortBorder;j++){ //在无序范围内进行交换
System.out.print("第"+(j+1)+"躺:");
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
isDone = false;
lastExchangeIndex = j;//记录最后一次交换的位置，后面的不需要再交换
}
System.out.println(Arrays.toString(arr));
}
sortBorder = lastExchangeIndex;//选定交换范围
if(isDone){ //如果一次交换都没有，说明已经有序了，跳出循环
break;
}
}
}
}
控制台信息：
第1次
第1躺:[5, 6, 4, 3, 7, 8, 9]
第2躺:[5, 4, 6, 3, 7, 8, 9]
第3躺:[5, 4, 3, 6, 7, 8, 9]
第4躺:[5, 4, 3, 6, 7, 8, 9]
第5躺:[5, 4, 3, 6, 7, 8, 9]
第6躺:[5, 4, 3, 6, 7, 8, 9]
第2次
第1躺:[4, 5, 3, 6, 7, 8, 9]
第2躺:[4, 3, 5, 6, 7, 8, 9]
第3次
第1躺:[3, 4, 5, 6, 7, 8, 9]
第4次
可以看到，一旦排序完成，立刻停止。
网友评论