冒泡排序可以简单用一句话来概括：有n个数就总共要排(n-1)趟，每趟要排(n-i-1)次。
裴新老师还做了优化，减少趟数。原理是：如果进行某趟排序时一次元素交换都没有发生，就说明该数组已经是有序的了，这时候就可以break跳出循环，不用进行下一趟了。
1 package com.bjsxt.sort.bubble; 2 3 import java.util.Arrays; 4 5 /** 6 * 考虑存在顺序，减少趟数 7 * 8 */ 9 public class BubbleSort { 10 public static void main(String[] args) { 11 int[] arr = {9,1,2,3,4}; 12 sort1(arr); 13 14 System.out.println("==========================="); 15 arr = new int[] {1,2,9,3,4}; 16 sortFinal(arr); 17 } 18 19 public static void sortFinal(int[] arr) { 20 boolean sorted = true; 21 int len = arr.length; 22 for(int j=0;j<len-1;j++) { //趟数 23 sorted = true; //假定有序 24 System.out.println("第" + (j+1) + "趟"); 25 for(int i=0;i<arr.length-1-j;i++) { //次数 26 System.out.print("第" + (i+1) + "次"); 27 if(arr[i]>arr[i+1]) { 28 int temp = arr[i]; 29 arr[i] = arr[i+1]; 30 arr[i+1] = temp; 31 sorted = false; //假定失败 32 } 33 System.out.println(Arrays.toString(arr)); 34 } 35 if(sorted) { 36 break; 37 } 38 } 39 } 40 41 public static void sort1(int[] arr) { 42 int len = arr.length; 43 for(int j=0;j<len-1;j++) { //趟数 44 System.out.println("第" + (j+1) + "趟"); 45 for(int i=0;i<arr.length-1-j;i++) { //次数 46 System.out.print("第" + (i+1) + "次"); 47 if(arr[i]>arr[i+1]) { 48 int temp = arr[i]; 49 arr[i] = arr[i+1]; 50 arr[i+1] = temp; 51 } 52 System.out.println(Arrays.toString(arr)); 53 } 54 } 55 } 56 57 }
输出结果是：
第1趟 第1次[1, 9, 2, 3, 4] 第2次[1, 2, 9, 3, 4] 第3次[1, 2, 3, 9, 4] 第4次[1, 2, 3, 4, 9] 第2趟 第1次[1, 2, 3, 4, 9] 第2次[1, 2, 3, 4, 9] 第3次[1, 2, 3, 4, 9] 第3趟 第1次[1, 2, 3, 4, 9] 第2次[1, 2, 3, 4, 9] 第4趟 第1次[1, 2, 3, 4, 9] =========================== 第1趟 第1次[1, 2, 9, 3, 4] 第2次[1, 2, 9, 3, 4] 第3次[1, 2, 3, 9, 4] 第4次[1, 2, 3, 4, 9] 第2趟 第1次[1, 2, 3, 4, 9] 第2次[1, 2, 3, 4, 9] 第3次[1, 2, 3, 4, 9]
可以看到，优化过的方法里只排了2趟。