不诗意的女程序猿不是好厨师~
转载请注明出处【From 李诗雨---https://blog.csdn.net/cjm2484836553/article/details/95004540】
源码地址见github:https://github.com/junmei520/DataStructureStudy/tree/master/src/algorithms
1.冒泡排序概念
排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐步移到后部，就像水底的气泡一样逐渐往上冒。
2.举个栗子并总结规则
下面我们以 2, 8, -1, 20, -6 这组数据为例，来一步一步进行冒泡排序：
最终排序后结果：-6 ，-1 ，2 ，8 ，20
由此我们总结出一些冒泡排序的规则：
（1）一共进行了【数组的大小-1】次大的循环。
（2）每一趟排序的次数在逐渐减少。
3.代码实现基础的冒泡排序
3.1先从冒泡排序的演变过程来一步一步分析
（此部分完整代码 对应 github上的 algorithms.BubbleSort1 类）
还是以上面的数组为实例，我们来一步一步分析：
第一趟排序 把最大的数排在最后 需要比较4次(即【arr.length-1】次
//第一趟排序 把最大的数排在最后
// 需要比较4次(即【arr.length-1】次)
int temp = 0;
for (int j = 0; j < arr.length - 1; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第一趟后的数组为：" + Arrays.toString(arr));
第二趟排序 把第二大的数排在倒数第二位
这次的比较次数比以第一趟的少1次，需要比较3次(即【arr.length-1-1】次)
//第二趟排序 把第二大的数排在倒数第二位
//这次的比较次数比以第一趟的少1次，需要比较3次(即【arr.length-1-1】次)
for (int j = 0; j < arr.length - 1 - 1; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第二趟后的数组为：" + Arrays.toString(arr));
第三趟排序 把第三大的数排在倒数第三位
这次的比较次数比以第一趟的少2次，需要比较2次(即【arr.length-1-2】次)
//第三趟排序 把第三大的数排在倒数第三位
//这次的比较次数比以第一趟的少2次，需要比价2次(即【arr.length-1-2】次)
for (int j = 0; j < arr.length - 1 - 2; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第三趟后的数组为：" + Arrays.toString(arr));
第四趟排序 把第四大的数排在倒数第四位
这次的比较次数比以第一趟的少3次，需要比较1次(即【arr.length-1-3】次)
//第四趟排序 把第四大的数排在倒数第四位
//这次的比较次数比以第一趟的少3次，需要比价1次(即【arr.length-1-3】次)
for (int j = 0; j < arr.length - 1 - 3; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第四趟后的数组为：" + Arrays.toString(arr));
打印结果：
3.2总结规律并合并简化代码
（此部分完整代码 对应 github上的 algorithms.BubbleSort2 类）
通过总结，我们可以看出，这四趟的比较代码基本相同，唯一不同的就是这里：
所以我们可以把不同的抽取出去，把相同的包起来，则可以改造成如下样子：
//创建原始数组
int[] arr = {2, 8, -1, 20, 80};
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "趟后的数组为：" + Arrays.toString(arr));
}
打印结果：
4.对冒泡排序进行适当的优化
4.1通过实例发现问题
先举个需要优化的例子：比如把 2,8，-1,20,80按从小到的顺序进行排序
一步一步来分析：
此时我们发现了问题，其实第三趟排序数组并没有发生任何变化，第四趟变化其实是多余的操作。我们本可以在第三趟排序后就提前结束冒泡排序的。
4.2优化的具体代码实现
（此部分完整代码 对应 github上的 algorithms.BubbleSort3 类）
思路：
根据上面的分析 我们可以定下一个这样的规则：如果某趟排序中，没有发生过一次交换，就可以提前结束冒泡排序，这个就是优化的方法。
那么我们不妨增加一个boolean 型的标记 flag，初始值为false ， 如果某趟排序中进行了次序交换则把flag置为true。在一趟排序结束后，就判断如果flag为false（说明此趟排序中没有发生过一次交换），则提前退出冒泡排序；如果flag为true,则重置为false,继续进行下一趟比较。
我们就以 2,8，-1,20,80 这组数据集为例，没有优化前打印结果是：
优化后的代码为：
//创建原始数组
int[] arr = {2, 8, -1, 20, 80};
boolean flag = false;//用于记录一趟排序中是否进行过交换
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
flag = true; //只要在某趟排序中进行了交换，就置为true
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "趟后的数组为：" + Arrays.toString(arr));
//一趟比较结束后，判断flag的值
if (!flag) { //如果为false,则可以提前结束冒泡排序(说明此趟排序中一次交换都没有)
return;
} else { //如果为true,则重置为false
flag = false;
}
}
优化后的打印结果：
果然少进行了一趟排序。
5.将冒泡排序封装成一个方法。
（此部分完整代码 对应 github上的 algorithms.BubbleSort4 类）
细心的我们可能已经发现，上面的代码太过于零散，那么我们不妨把它封装成一个方法，这样当数组数据发生变化时，我们只要调用方法就可以了。
public class BubbleSort4 {
public static void main(String[] args) {
//创建原始数组
int[] arr = {2, 8, -1, 20, 80};
//测试冒泡排序方法
System.out.println("排序前：" + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
/**
* 封装的冒泡排序方法
*/
private static void bubbleSort(int[] arr) {
boolean flag = false;//用于记录一趟排序中是否进行过交换
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
//如果前面的数比后面的数大，就进行交换
if (arr[j] > arr[j + 1]) {
flag = true; //只要在某趟排序中进行了交换，就置为true
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// System.out.println("第" + (i + 1) + "趟后的数组为：" + Arrays.toString(arr));
//一趟比较结束后，判断flag的值
if (!flag) { //如果为false,则可以提前结束冒泡排序(说明此趟排序中一次交换都没有)
return;
} else { //如果为true,则重置为false
flag = false;
}
}
}
}
源码地址见github:https://github.com/junmei520/DataStructureStudy/tree/master/src/algorithms
积累点滴，做好自己~
