什么是冒泡排序？
摘自漫畫算法：
冒泡排序的英文是bubble sort，它是一種基礎(chǔ)的交換排序。
大家一定都喝過汽水，汽水中常常有許多小小的氣泡嘩啦啦飄到上面來。這是因為組成小氣泡的二氧化碳比水輕，所以小氣泡可以一點一點地向上浮動。
而冒泡排序之所以叫冒泡排序，正是因為這種排序算法的每一個元素都可以像小氣泡一樣，根據(jù)自身大小，一點一點地向著數(shù)組的一側(cè)移動。
例子：
有8個數(shù)字組成一個無序數(shù)列{5,8,6,3,9,2,1,7}，希望按照從小到大的順序?qū)ζ溥M(jìn)行排序。
按照冒泡排序的思想，我們要把相鄰的元素兩兩比較，當(dāng)一個元素大于右側(cè)相鄰元素時，交換它們的位置，當(dāng)一個元素小于或等于右側(cè)相鄰元素時，位置不變。
過程如下：
這樣一來，元素9作為數(shù)組中最大的元素，就像是汽水里的小氣泡一樣，“漂”到了最右側(cè)。
這時，冒泡排序的第一輪就結(jié)束了。數(shù)組最右側(cè)的元素9的位置可以認(rèn)為是一個有序區(qū)域，有序區(qū)域目前只有一個元素。
下面，讓我們來進(jìn)行第二輪排序。
過程如下：
第二輪排序結(jié)束后，數(shù)組右側(cè)的有序區(qū)域有了2個元素，順序如下：
后續(xù)的交換細(xì)節(jié)，就不再詳細(xì)描述了，第三輪到第七輪的狀態(tài)如下：
到此為止，所有元素都是有序的了，這就是冒泡排序的整體思路。
冒牌排序是一種穩(wěn)定排序，值相等的元素并不會打亂原本的順序。由于該排序算法的每一輪都要遍歷所有元素，總共遍歷（元素數(shù)量 - 1）輪，所以平均時間復(fù)雜度是O(n2)。
冒泡排序的實現(xiàn)
整體代碼
import java.util.Arrays;
/**
* 描述：冒泡排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
整體代碼非常的簡單，使用雙循環(huán)進(jìn)行排序。外部循環(huán)控制所有的回合，內(nèi)部循環(huán)實現(xiàn)每一輪的冒泡處理，先進(jìn)行元素比較，再進(jìn)行元素交換。
優(yōu)化冒泡排序
方式1
原始的冒泡排序有哪些可以優(yōu)化的點呢？
在剛才描述的排序細(xì)節(jié)，仍然以{5,8,6,3,9,2,1,7}這個數(shù)列為例，當(dāng)排序算法分別執(zhí)行到第6輪、第7輪時，數(shù)列狀態(tài)如下：
很明顯可以看出，經(jīng)過第6輪排序后，整個數(shù)列已經(jīng)是有序的了?？梢耘判蛩惴ㄈ匀痪ぞI(yè)業(yè)地繼續(xù)執(zhí)行了第7輪排序。
在這種情況下，如果能判斷出數(shù)列已經(jīng)有序，并做出標(biāo)記，那么剩下的幾輪排序就不必執(zhí)行了，可以提前結(jié)束工作。
優(yōu)化后的代碼：
import java.util.Arrays;
/**
* 描述：冒泡排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
//有序標(biāo)記，每一輪的初始值都是true
boolean isSorted = true;
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//因為有元素進(jìn)行交換，所以不是有序的，標(biāo)記變?yōu)閒alse
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
與優(yōu)化前的代碼相比，優(yōu)化后的代碼做了小小的改動，利用布爾變量isSorted作為標(biāo)記。如果在本輪排序中，有元素交換，則說明數(shù)列無序；如果沒有元素交換，則說明數(shù)列已經(jīng)是有序的了，然后直接跳出大循環(huán)。
方式2
為了說明問題，這次以一個新的數(shù)列為例。
這個數(shù)列的特點是前半部分的元素（3、4、2、1）無序，后半部分的元素（5、6、7、8）按升序排列，并且后半部分元素中的最小值也大于前半部分元素的最大值。
下面按照冒泡排序的思路來進(jìn)行排序，看看具體的效果。
第1輪：
元素4和5進(jìn)行比較，由于4小于5，所以位置不變。
元素5和6進(jìn)行比較，由于5小于6，所以位置不變。
元素6和7進(jìn)行比較，由于6小于7，所以位置不變。
元素7和8進(jìn)行比較，由于7小于8，所以位置不變。
第1輪結(jié)束，數(shù)列的有序區(qū)域包含1個元素。
第2輪：
元素3和2進(jìn)行比較，由于3大于2，所以元素3與2進(jìn)行交換。
元素3和1進(jìn)行比較，由于3大于1，所以元素3與1進(jìn)行交換。
元素3和4進(jìn)行比較，由于3小于4，所以位置不變。
元素4和5進(jìn)行比較，由于4小于5，所以位置不變。
元素5和6進(jìn)行比較，由于5小于6，所以位置不變。
元素6和7進(jìn)行比較，由于6小于7，所以位置不變。
元素7和8進(jìn)行比較，由于7小于8，所以位置不變。
此時第2輪結(jié)束，數(shù)列有序取悅包含2個元素。
問題：其實右側(cè)的許多元素已經(jīng)是有序的了，可是每一輪還是白白地浪費(fèi)時間進(jìn)行比較。
這個問題的關(guān)鍵點在于對數(shù)列有序區(qū)域的界定。
按照現(xiàn)在的邏輯，有序區(qū)的長度和排序的輪樹是相等的。例如第1輪排序過后的有序區(qū)域長度是1，第2輪過后有序區(qū)域的長度為2 ......。
實際上，數(shù)列真正的有序區(qū)域可能會大于這個長度，例如上述例子中在第2輪排序時，后面的5個元素實際上都已經(jīng)屬于有序區(qū)域了。因此后面的多次元素比較是沒有意義的。
那么，如何避免這種情況呢？我們可以在每一輪排序后，記錄下來最后一次元素交換的位置，該位置即為無序數(shù)列的邊界，再往后就是有序區(qū)域了。
優(yōu)化后的代碼：
import java.util.Arrays;
/**
* 描述：冒泡排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
// 記錄最后一次交換的位置
int lastExchangeIndex = 0;
// 無序數(shù)列的邊界，每次比較只需要比到這里為止
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
//有序標(biāo)記，每一輪的初始值都是true
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//因為有元素進(jìn)行交換，所以不是有序的，標(biāo)記變?yōu)閒alse
isSorted = false;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
在優(yōu)化方式2的代碼中，sortBorder就是無序數(shù)列的邊界。在每一輪排序過程中，處于sortBorder之后的元素就不需要再進(jìn)行比較了，肯定是有序的。
雞尾酒排序
冒泡排序的每一個元素都可以像小氣泡一樣，根據(jù)自身大小，一點一點地向著數(shù)組的一側(cè)移動。算法的每一輪都是從左到右來比較元素，進(jìn)行單向的位置交換的。
那么雞尾酒排序做了什么樣的優(yōu)化呢？
雞尾酒排序的元素比較和交換過程是雙向的。
例子：
由8個數(shù)字組成一個無需數(shù)列{2,3,4,5,6,7,8,1}，希望對其進(jìn)行從小到大的排序。
如果按照冒泡排序的思路，排序過程如下：
問題：元素2、3、4、5、6、7、8已經(jīng)是有序的了，只有元素1的位置不對，卻還要進(jìn)行7輪排序！雞尾酒排序正是要解決這個問題的。
那么雞尾酒排序是什么樣子的呢？過程如下：
第1輪：
此時和冒泡排序一樣， 元素8和1進(jìn)行交換。
第2輪：
此時開始不一樣了，我們反過來從右往左比較并進(jìn)行交換。
第3輪（雖然實際上已經(jīng)有序了，但是流程并沒有結(jié)束）：
在雞尾酒排序的第3輪，需要重新從左向右比較并進(jìn)行交換。
元素1和2進(jìn)行比較，由于1小于2，所以位置不變。
元素2和3進(jìn)行比較，由于2小于3，所以位置不變。
元素3和4進(jìn)行比較，由于3小于4，所以位置不變。
元素4和5進(jìn)行比較，由于4小于5，所以位置不練。
元素5和6進(jìn)行比較，由于5小于6，所以位置不變。
元素6和7進(jìn)行比較，由于6小于7，所以位置不變。
元素7和8進(jìn)行比較，由于7小于8，所以位置不變。
此時沒有元素進(jìn)行交換，證明已經(jīng)有序了，排序結(jié)束。
這就是雞尾酒排序的思路。排序過程就是鐘擺一樣，第1輪從左到右，第2輪從右到左，第3輪在從左到右，本來需要7輪排序的場景，只用3輪就解決了。
代碼如下：
import java.util.Arrays;
/**
* 描述：雞尾酒排序
* <p>
* Create By ZhangBiao
* 2020/5/20
*/
public class BubbleSort {
public static void sort(int arr[]) {
int temp = 0;
for (int i = 0; i < arr.length / 2; i++) {
// 有序標(biāo)記，每一輪的初始值都是true
boolean isSorted = true;
// 奇數(shù)輪，從左向右比較和交換
for (int j = i; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 有元素交換，所以不是有序的，標(biāo)記變?yōu)閒alse
isSorted = false;
}
}
if (isSorted) {
break;
}
// 在偶數(shù)輪之前，將isSorted重新標(biāo)記為true
isSorted = true;
// 偶數(shù)輪，從右向左比較和交換
for (int j = arr.length - i - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
// 因為有元素進(jìn)行交換，所以不是有序的，標(biāo)記變?yōu)閒alse
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
這段代碼是雞尾酒排序的原始實現(xiàn)。代碼外層的大循環(huán)控制著所有排序回合，大循環(huán)內(nèi)包含2個小循環(huán)，第1個小循環(huán)從左向右比較并交換元素，第2個小循環(huán)從右向左比較并交換元素。
