简介
冒泡排序是一种非常主流的排序算法，冒泡排序的英文（Bubble sort），它是一种基础的交换排序。
原理 ： 比较两个相邻的元素，将值大的元素交换至右端。
思想： 把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置。当一个元素小于或等于右侧相邻元素时，位置不变。
举例说明：要排序数组：int[] array={5,8,6,3,9,2,1,7};
第一趟排序：
第一次排序：5 和 8 比较，5 小于 8 ，位置不变： 5,8,6,3,9,2,1,7
第二次排序：8 和 6 比较，8 大于 6 ，交换位置： 5,6,8,3,9,2,1,7
第三次排序：8 和 3 比较，8 大于 3 ，交换位置： 5,6,3,8,9,2,1,7
第四次排序：8 和 9 比较，8 小于 9 ，位置不变： 5,6,3,8,9,2,1,7
第五次排序：9 和 2 比较，9 大于 2 ，交换位置： 5,6,3,8,2,9,1,7
第六次排序：9 和 1 比较，9 小于 1 ，交换位置： 5,6,3,8,2,1,9,7
第七次排序：9 和 7 比较，9 小于 7 ，交换位置： 5,6,3,8,2,1,7,9
第二趟排序：
第一次排序：5 和 6 比较，5 小于 6 ，位置不变： 5,6,3,8,2,1,7,9
第二次排序：6 和 3 比较，6 大于 3 ，交换位置： 5,3,6,8,2,1,7,9
第三次排序：6 和 8 比较，6 小于 8 ，位置不变： 5,6,3,8,2,1,7,9
第四次排序：8 和 2 比较，8 大于 2 ，交换位置： 5,6,3,2,8,1,7,9
第五次排序：8 和 1 比较，8 大于 1 ，交换位置： 5,6,3,2,1,8,7,9
第六次排序：8 和 7 比较，8 大于 7 ，交换位置： 5,6,3,2,1,7,8,9
第七次排序：8 和 9 比较，8 小于 9 ，位置不变： 5,6,3,2,1,7,8,9
第三趟排序：
第一次排序：5 和 6 比较，5 小于 6 ，位置不变： 5,6,3,2,1,7,8,9
第二次排序：6 和 3 比较，6 大于 3 ，交换位置： 5,3,6,2,1,7,8,9
第三次排序：6 和 2 比较，6 大于 2 ，交换位置： 5,3,2,6,1,7,8,9
第四次排序：6 和 1 比较，6 大于 1 ，交换位置： 5,3,2,1,6,7,8,9
第五次排序：6 和 7 比较，6 小于 7 ，位置不变： 5,3,2,1,6,7,8,9
第六次排序：7 和 8 比较，7 小于 8 ，位置不变： 5,3,2,1,6,7,8,9
第七次排序：8 和 9 比较，8 小于 9 ，位置不变： 5,3,2,1,6,7,8,9
第四趟排序：
第一次排序：5 和 3 比较，5 大于 3 ，交换位置： 3,5,2,1,6,7,8,9
第二次排序：5 和 2 比较，5 大于 2 ，交换位置： 3,2,5,1,6,7,8,9
第三次排序：5 和 1 比较，5 大于 1 ，交换位置： 3,2,1,5,6,7,8,9
第四次排序：5 和 6 比较，5 小于 6 ，位置不变： 3,2,1,5,6,7,8,9
第五次排序：6 和 7 比较，6 小于 7 ，位置不变： 3,2,1,5,6,7,8,9
第六次排序：7 和 8 比较，7 小于 8 ，位置不变： 3,2,1,5,6,7,8,9
第七次排序：8 和 9 比较，8 小于 9 ，位置不变： 3,2,1,5,6,7,8,9
第五趟排序：
第一次排序：3 和 2 比较，3 大于 2 ，交换位置： 2,3,1,5,6,7,8,9
第二次排序：3 和 1 比较，3 大于 1 ，交换位置： 2,1,3,5,6,7,8,9
第三次排序：3 和 5 比较，3 小于 5 ，位置不变： 2,1,3,5,6,7,8,9
第四次排序：5 和 6 比较，5 小于 6 ，位置不变： 2,1,3,5,6,7,8,9
第五次排序：6 和 7 比较，6 小于 7 ，位置不变： 2,1,3,5,6,7,8,9
第六次排序：7 和 8 比较，7 小于 8 ，位置不变： 2,1,3,5,6,7,8,9
第七次排序：8 和 9 比较，8 小于 9 ，位置不变： 2,1,3,5,6,7,8,9
第六趟排序：
第一次排序：2 和 1 比较，2 大于 1 ，交换位置： 1,2,3,5,6,7,8,9
第二次排序：2 和 3 比较，2 小于 3 ，位置不变： 1,2,3,5,6,7,8,9
第三次排序：3 和 5 比较，3 小于 5 ，位置不变： 1,2,3,5,6,7,8,9
第四次排序：5 和 6 比较，5 小于 6 ，位置不变： 1,2,3,5,6,7,8,9
第五次排序：6 和 7 比较，6 小于 7 ，位置不变： 1,2,3,5,6,7,8,9
第六次排序：7 和 8 比较，7 小于 8 ，位置不变： 1,2,3,5,6,7,8,9
第七次排序：8 和 9 比较，8 小于 9 ，位置不变： 1,2,3,5,6,7,8,9
第七趟排序：
第一次排序：1 和 2 比较，1 小于 2 ，位置不变： 1,2,3,5,6,7,8,9
第二次排序：2 和 3 比较，2 小于 3 ，位置不变： 1,2,3,5,6,7,8,9
第三次排序：3 和 5 比较，3 小于 5 ，位置不变： 1,2,3,5,6,7,8,9
第四次排序：5 和 6 比较，5 小于 6 ，位置不变： 1,2,3,5,6,7,8,9
第五次排序：6 和 7 比较，6 小于 7 ，位置不变： 1,2,3,5,6,7,8,9
第六次排序：7 和 8 比较，7 小于 8 ，位置不变： 1,2,3,5,6,7,8,9
第七次排序：8 和 9 比较，8 小于 9 ，位置不变： 1,2,3,5,6,7,8,9
排序结果 ： 1,2,3,5,6,7,8,9
/**
* 冒泡排序
* 定义 ： 我们要把相邻的两个元素两两比较，当一个元素大于右侧相邻元素时，
* 交换他们的位置 ： 当一个元素小于或等于相邻右侧元素时，位置不变
*/
public class demo1 {
public static void main(String[] args) {
int array[] = {5,8,6,3,9,2,1,7};
sortBig(array);
System.out.println("大到小排列："+ Arrays.toString(array));
sortSmall(array);
System.out.println("小到大排列："+ Arrays.toString(array));
}
/**
* 从大到小排序方法
* @param array 数组
*/
private static void sortBig(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 ; j++) {
int temp = 0;
if(array[i] > array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
/**
* 从小到大排序
* @param array 数组
*/
private static void sortSmall(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 ; j++) {
int temp = 0;
if(array[j] > array[j +1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
代码使用双循环进行排序 外部循环控制所有的回合，内部循环实现每一轮的冒泡处理，先进行元素比较，再进行元素交换。
执行结果：
大到小排列：[9, 8, 7, 6, 5, 3, 2, 1]
小到大排列：[1, 2, 3, 5, 6, 7, 8, 9]
优化
让我们回顾一下刚才描述的排序细节，{5,8,6,3,9,2,1,7}这个数列，当排序算法分别执行到第6、第7轮时
很明显可以看出，经过第六轮的时候，整个数列已经是有序的了。可是排序算法仍然执行了第七轮
在这种情况下，如果能判断出数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了，可以提前结束工作。
冒泡排序代码优化：
/**
* 冒泡排序优化
* 定义 ： 我们要把相邻的两个元素两两比较，当一个元素大于右侧相邻元素时，
* 交换他们的位置 ： 当一个元素小于或等于相邻右侧元素时，位置不变
*/
public class demo1 {
public static void main(String[] args) {
int array[] = {5,8,6,3,9,2,1,7};
sortBig(array);
System.out.println("大到小排列："+ Arrays.toString(array));
sortSmall(array);
System.out.println("小到大排列："+ Arrays.toString(array));
}
/**
* 从大到小排序方法
* @param array 数组
*/
private static void sortBig(int[] array) {
for (int i = 0; i < array.length; i++) {
//标记
boolean flag = true;
for (int j = 0; j < array.length - 1 ; j++) {
int temp = 0;
if(array[i] > array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
//有元素在交换，所以不是有序的
flag = false;
}
}
if(flag){
break;
}
}
}
/**
* 从小到大排序
* @param array 数组
*/
private static void sortSmall(int[] array) {
for (int i = 0; i < array.length; i++) {
//标记
boolean flag = true;
for (int j = 0; j < array.length - 1 ; j++) {
int temp = 0;
if(array[j] > array[j +1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
//有元素在交换，所以不是有序的
flag = false;
}
}
if(flag){
break;
}
}
}
}
利用 boolean 变量 flag 作为标记。如果本轮排序中，元素有交换，则列表是无序的，如果没有元素交换，则是有序的，直接跳出大循环, 进一步提升了性能。
个人博客地址：http://blog.yanxiaolong.cn ｜ <font color = "orange"> 『纵有疾风起，人生不言弃』 </font>
