不詩意的女程序猿不是好廚師~
轉(zhuǎn)載請注明出處【From 李詩雨---https://blog.csdn.net/cjm2484836553/article/details/95004540】
源碼地址見github:https://github.com/junmei520/DataStructureStudy/tree/master/src/algorithms
1.冒泡排序概念
排序序列從前向后（從下標(biāo)較小的元素開始），依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐步移到后部，就像水底的氣泡一樣逐漸往上冒。
2.舉個栗子并總結(jié)規(guī)則
下面我們以 2, 8, -1, 20, -6 這組數(shù)據(jù)為例，來一步一步進(jìn)行冒泡排序：
最終排序后結(jié)果：-6 ，-1 ，2 ，8 ，20
由此我們總結(jié)出一些冒泡排序的規(guī)則：
（1）一共進(jìn)行了【數(shù)組的大小-1】次大的循環(huán)。
（2）每一趟排序的次數(shù)在逐漸減少。
3.代碼實(shí)現(xiàn)基礎(chǔ)的冒泡排序
3.1先從冒泡排序的演變過程來一步一步分析
（此部分完整代碼 對應(yīng) github上的 algorithms.BubbleSort1 類）
還是以上面的數(shù)組為實(shí)例，我們來一步一步分析：
第一趟排序 把最大的數(shù)排在最后 需要比較4次(即【arr.length-1】次
//第一趟排序 把最大的數(shù)排在最后
// 需要比較4次(即【arr.length-1】次)
int temp = 0;
for (int j = 0; j < arr.length - 1; j++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第一趟后的數(shù)組為：" + Arrays.toString(arr));
第二趟排序 把第二大的數(shù)排在倒數(shù)第二位
這次的比較次數(shù)比以第一趟的少1次，需要比較3次(即【arr.length-1-1】次)
//第二趟排序 把第二大的數(shù)排在倒數(shù)第二位
//這次的比較次數(shù)比以第一趟的少1次，需要比較3次(即【arr.length-1-1】次)
for (int j = 0; j < arr.length - 1 - 1; j++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第二趟后的數(shù)組為：" + Arrays.toString(arr));
第三趟排序 把第三大的數(shù)排在倒數(shù)第三位
這次的比較次數(shù)比以第一趟的少2次，需要比較2次(即【arr.length-1-2】次)
//第三趟排序 把第三大的數(shù)排在倒數(shù)第三位
//這次的比較次數(shù)比以第一趟的少2次，需要比價2次(即【arr.length-1-2】次)
for (int j = 0; j < arr.length - 1 - 2; j++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第三趟后的數(shù)組為：" + Arrays.toString(arr));
第四趟排序 把第四大的數(shù)排在倒數(shù)第四位
這次的比較次數(shù)比以第一趟的少3次，需要比較1次(即【arr.length-1-3】次)
//第四趟排序 把第四大的數(shù)排在倒數(shù)第四位
//這次的比較次數(shù)比以第一趟的少3次，需要比價1次(即【arr.length-1-3】次)
for (int j = 0; j < arr.length - 1 - 3; j++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第四趟后的數(shù)組為：" + Arrays.toString(arr));
打印結(jié)果：
3.2總結(jié)規(guī)律并合并簡化代碼
（此部分完整代碼 對應(yīng) github上的 algorithms.BubbleSort2 類）
通過總結(jié)，我們可以看出，這四趟的比較代碼基本相同，唯一不同的就是這里：
所以我們可以把不同的抽取出去，把相同的包起來，則可以改造成如下樣子：
//創(chuàng)建原始數(shù)組
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++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "趟后的數(shù)組為：" + Arrays.toString(arr));
}
打印結(jié)果：
4.對冒泡排序進(jìn)行適當(dāng)?shù)膬?yōu)化
4.1通過實(shí)例發(fā)現(xiàn)問題
先舉個需要優(yōu)化的例子：比如把 2,8，-1,20,80按從小到的順序進(jìn)行排序
一步一步來分析：
此時我們發(fā)現(xiàn)了問題，其實(shí)第三趟排序數(shù)組并沒有發(fā)生任何變化，第四趟變化其實(shí)是多余的操作。我們本可以在第三趟排序后就提前結(jié)束冒泡排序的。
4.2優(yōu)化的具體代碼實(shí)現(xiàn)
（此部分完整代碼 對應(yīng) github上的 algorithms.BubbleSort3 類）
思路：
根據(jù)上面的分析 我們可以定下一個這樣的規(guī)則：如果某趟排序中，沒有發(fā)生過一次交換，就可以提前結(jié)束冒泡排序，這個就是優(yōu)化的方法。
那么我們不妨增加一個boolean 型的標(biāo)記 flag，初始值為false ， 如果某趟排序中進(jìn)行了次序交換則把flag置為true。在一趟排序結(jié)束后，就判斷如果flag為false（說明此趟排序中沒有發(fā)生過一次交換），則提前退出冒泡排序；如果flag為true,則重置為false,繼續(xù)進(jìn)行下一趟比較。
我們就以 2,8，-1,20,80 這組數(shù)據(jù)集為例，沒有優(yōu)化前打印結(jié)果是：
優(yōu)化后的代碼為：
//創(chuàng)建原始數(shù)組
int[] arr = {2, 8, -1, 20, 80};
boolean flag = false;//用于記錄一趟排序中是否進(jìn)行過交換
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
flag = true; //只要在某趟排序中進(jìn)行了交換，就置為true
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "趟后的數(shù)組為：" + Arrays.toString(arr));
//一趟比較結(jié)束后，判斷flag的值
if (!flag) { //如果為false,則可以提前結(jié)束冒泡排序(說明此趟排序中一次交換都沒有)
return;
} else { //如果為true,則重置為false
flag = false;
}
}
優(yōu)化后的打印結(jié)果：
果然少進(jìn)行了一趟排序。
5.將冒泡排序封裝成一個方法。
（此部分完整代碼 對應(yīng) github上的 algorithms.BubbleSort4 類）
細(xì)心的我們可能已經(jīng)發(fā)現(xiàn)，上面的代碼太過于零散，那么我們不妨把它封裝成一個方法，這樣當(dāng)數(shù)組數(shù)據(jù)發(fā)生變化時，我們只要調(diào)用方法就可以了。
public class BubbleSort4 {
public static void main(String[] args) {
//創(chuàng)建原始數(shù)組
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;//用于記錄一趟排序中是否進(jìn)行過交換
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
//如果前面的數(shù)比后面的數(shù)大，就進(jìn)行交換
if (arr[j] > arr[j + 1]) {
flag = true; //只要在某趟排序中進(jìn)行了交換，就置為true
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// System.out.println("第" + (i + 1) + "趟后的數(shù)組為：" + Arrays.toString(arr));
//一趟比較結(jié)束后，判斷flag的值
if (!flag) { //如果為false,則可以提前結(jié)束冒泡排序(說明此趟排序中一次交換都沒有)
return;
} else { //如果為true,則重置為false
flag = false;
}
}
}
}
源碼地址見github:https://github.com/junmei520/DataStructureStudy/tree/master/src/algorithms
積累點(diǎn)滴，做好自己~
