1、基本介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，再进行)。
2、演示冒泡过程的例子 【画图理解】
原始数组：3, 9, -1, 10, -2
第一趟排序 如果相邻的元素逆序就交换
【交换完之后的结果】
(1) 3, 9, -1, 10, -2
(2) 3, -1, 9, 10, -2 //交换
(3) 3, -1, 9, 10, -2
(4) 3, -1, 9, -2, 10 //交换
int temp = 0; //临时变量，做交换使用
for(int i=0;i<arr.length-1-0;i++){
//如果前面的数比后面的数大，就进行交换处理
if(arr[i]>arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
第二趟排序:3, -1, 9, -2, 10
【交换完之后的结果】
(1) -1, 3, 9, -2, 10 //交换
(2) -1, 3, 9, -2, 10
(3) -1, 3, -2, 9, 10 //交换
int temp = 0; //临时变量，做交换使用
for(int i=0;i<arr.length-1-1;i++){
//如果前面的数比后面的数大，就进行交换处理
if(arr[i]>arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
第三趟排序:-1, 3, -2, 9, 10
【交换完之后的结果】
(1) -1, 3, -2, 9, 10
(2) -1, -2, 3, 9, 10 //交换
int temp = 0; //临时变量，做交换使用
for(int i=0;i<arr.length-1-2;i++){
//如果前面的数比后面的数大，就进行交换处理
if(arr[i]>arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
第四趟排序:-1, -2, 3, 9, 10
【交换完之后的结果】
(1) -2, -1, 3, 9, 10 //交换
int temp = 0; //临时变量，做交换使用
for(int i=0;i<arr.length-1-3;i++){
//如果前面的数比后面的数大，就进行交换处理
if(arr[i]>arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
小结冒泡排序规则
(1) 一共进行 数组的大小-1次大的循环；
(2)每一趟排序的次数在逐渐的减少；
(3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化。
3、代码实例
//时间复杂度o(n^2)
for(int j=0;j<arr.length-1;j++){
int temp = 0; //临时变量，做交换使用
for(int i=0;i<arr.length-1-j;i++){
//如果前面的数比后面的数大，就进行交换处理
if(arr[i]>arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
System.out.printf("第%d趟排序后的数组：\n",(j+1));
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
优化： 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。
boolean flag = false; //表示变量，表示是否进行过交换，默认为false
for(int j=0;j<arr.length-1;j++){
int temp = 0; //临时变量，做交换使用
for(int i=0;i<arr.length-1-j;i++){
//如果前面的数比后面的数大，就进行交换处理
if(arr[i]>arr[i+1]){
flag = true; //说明有交换
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
//判断
if(flag == false){ //说明在一趟排序中一次交换都没有
break;
}else{
flag = false; //交换过，重置flag，进行下次判断
}
}
之前这种比较思路是每次找找最大值(对升序而言)
我个人习惯的是另一种写法，思路是找最小值(对升序而言)【画图理解】
代码：
public static void BubbleSortTest(int[] arr){
int temp = 0;
boolean flag = false;
for(int i=0;i<arr.length-1;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
flag = true;
temp = arr[i];
arr[i] =arr[j];
arr[j] = temp;
}
}
//判断
if(flag == false){ //说明在一趟排序中一次交换都没有
break;
}else{
flag = false; //交换过，重置flag，进行下次判断
}
}
}
