冒泡排序分從大到小和從小到大兩種排序方式。它們的唯一區别就是兩個數交換的條件不同，從大到小排序是前面的數比後面的小的時候交換，而從小到大排序是前面的數比後面的數大的時候交換。我這裡隻說 從小到大的排序方式。

冒泡排序的原理：從第一個數開始，依次往後比較，如果前面的數比後面的數大就交換，否則不作處理。這就類似燒開水時，壺底的水泡往上冒的過程。

一、 圖解分析

現以數組[8,7,6,4,5]為例，我們通過将這個數組按從小到大的方式排序，來說明冒泡排序的過程。

第一次循環：此次循環的多次比較交換，使最大的數字8冒到最上面。

第二次循環：此次循環中的多次比較和交換，使7往上冒，最終排到倒數第二個位置。

你會發現，這次循環比前面少一次循環比較。

這是因為第一次循環時已經把最大的8排到最上面的位置了，這次排序肯定不會去占用最上面的位置的，所以此時比較次數可以比前面少一次。

第三次循環：同理，此時6會往上冒。比較次數同理又會比前面少一次。

此時看着最後的結果已經是從小到大了，這是因為在原始數組中，5就在4的上面。

但實際我們不知道5是在4的上面，我們就得繼續完成最後一次循環比較。

第四次循環： 5已經排在4的上面了，比較後不交換。

二、代碼實現

總結前面的圖解，數組長度設為n。外層共循環了n-1次，外層循環增加一次，對應内層循環就 減少一次。

外層循環為：for (int i = 0; i < arr.length-1; i ) 内層循環為：for (int j = 0; j < arr.length - 1 - i; j )

int[] arr = {8, 7, 6, 4, 5}; 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]) { int temp = arr[j]; arr[j] = arr[j 1]; arr[j 1] = temp; } } }

需要注意的是，在裡層的for循環裡，j的取值範圍是arr.lenght - 1 - i。

三、冒泡排序算法的優化

具體的優化得看具體的情況

1. 減少外層循環次數的優化

如有數組[8,7,6,1,2,3,4,5]，當我們将8、7、6三個數都排在後面後，其實就不需要繼續循環比較了。

那我們如何知道後面不再需要比較了呢？答案就是如果該次循環沒有發生一次數的交換，就說明數組已經排好序了，那麼後面的循環比較就可以停止了。

代碼如下：

int[] arr = {8, 7, 6, 1, 2, 3, 4, 5}; // flag: 在一次循環中是否發生過數據交換。true：表示發生過交換，false：表示未發生過交換 boolean flag = true; for (int i = 0; i < arr.length - 1; i ) { // 如果未發生交換，則break if (!flag) { break; } flag = false; // 每次循環都先置為false，即認為不會發生交換 for (int j = 0; j < arr.length - i - 1; j ) { if (arr[j] > arr[j 1]) { flag = true;// 發生了交換 int temp = arr[j]; arr[j] = arr[j 1]; arr[j 1] = temp; } } System.out.println(i); }

從輸出結果看，外層循環隻循環了4次，而不會是7次。

2. 減少内層循環次數的優化

如有數組[2, 4, 3, 1, 5, 6, 7, 8, 9]，你會發現，從5開始都是不用比較和循環了。所以我們要想辦法減少後面的循環和比較。

我們可以發現，當我們把4交換到5前面後，後面的每次循環裡都不再發生交換。即，如果我們将第一次出現該次不再交換數據時的位置下标找到，然後把這個值作為内層循環j的上限值。這樣内層循環就會減少一些循環。所以内層循環的 j 的上限值是動态值。

代碼如下：

int[] arr = {4, 2, 3, 1, 5, 6, 7, 8, 9}; // flag: 在一次循環中是否發生過數據交換。true：表示發生過交換，false：表示未發生過交換 boolean flag = true; // 上一次内層循環上界值，在第一次循環時與arr.length-1-i相等，即：arr.length-1。也就是說默認是最後一個 int k = arr.length - 1; for (int i = 0; i < arr.length - 1; i ) { // 如果未發生交換，則break if (!flag) { break; } // 每次循環都先置為false，即認為不會發生交換 flag = false; // 記錄上一次内層循環時最後一次交換的位置 int last = 0; for (int j = 0; j < k; j ) { if (arr[j] > arr[j 1]) { // 發生了交換 flag = true; // 記錄每次交換的位置 last = j; int temp = arr[j]; arr[j] = arr[j 1]; arr[j 1] = temp; } } // 讓下一次循環的上界值變成此次循環的最後一次交換的位置 k = last; }

k為動态值有個好處，即随時動态調整上一次最後交換的位置。這樣做的好處是，當遇到數組中有緊挨着的數是連續的時候就會在下一次循環時省略它們的比較。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!