圖解算法：冒泡排序
0****1
故事起源
幼兒園放學，小朋友們集合，需要先從低到高排隊，應該怎麼排呢？
02
開始行動
小 K 身高 180，是班裏最高的，自然得往後排啦。小 K 先和身後的小 B 比較，然後和小 B 交換。
小 K 接着和身後的小 D 比較，然後和小 D 交換。
經過和 4 個小朋友交換位置，小 K 終於找到自己的位置啦。
上面的過程其實就是冒泡排序的核心思想了。
03
冒泡排序
爲描述方便，用下面的數組模擬小朋友的交換過程。
核心思想 (升序)：
從首位置開始，依次比較前後兩個數，如果前面的數比後面的數大，就交換兩個數。這樣第 1 輪結束後，最大的數就會移動到最後的位置。對剩餘元素重複執行 N-1 次，整個數組有序。因爲像空氣上浮到水面，最大的元素會慢慢浮到最後，所以冒泡因此得名。
3.1
第 1 輪
執行完成後，最大的元素歸位。
3.2
第 2 輪
第 2 輪接着對前面剩餘的 N-1 個元素重複上面步驟，第 2 大的元素歸位。
3.3
第 3 輪
第 3 輪對前面剩餘的 N-2 個元素重複上面步驟，第 3 大的元素歸位。
總共執行 N-1 次操作，所有元素歸位。
3.4
代碼實現
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}04
問題及優化
4.1
迭代輪次優化
如果原數組爲如下情況，那麼在執行完第 1 輪後，整個數組已經有序，後面的輪次沒必要執行，可以針對這種情況做一次優化改進。
改進點 1：
如果某一輪沒有發生過交換，說明數組已經有序，那麼以後也不會發生交換，此時可以終止迭代。
代碼實現
for (int i = 0; i < n - 1; ++i) {
// flag標記是否有交換
bool flag = true;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
flag = false;
}
}
if (flag) {
break;
}
}4.2
掃描範圍優化
如果爲以下情況，我們會發現最後的 6 和 8 所處的位置和最終排序完成的位置一樣，說明過程中他們的位置不會發生變化。
上一輪最後交換的位置，在下一輪時，此位置後面的數也不會再發生交換。
改進點 2：
記錄每一次最後發生交換的位置，下一輪只需要掃描到此位置的前一個即可。
代碼實現
// 記錄最後交換的位置
int position = 0;
int len = n - 1;
for (int i = 0; i < n - 1; ++i) {
// flag標記是否有交換
bool flag = true;
for (int j = 0; j < len; ++j) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
flag = false;
position = j;
}
}
len = position;
if (flag) {
break;
}
}05
總結
冒泡排序是比較簡單的一種排序算法，核心思想就是比較相鄰的兩個數，但效率比較低所以可做一些優化。時間複雜度爲 O(N^2)，數據規模較小時可採用，但數據過大時就不建議採用冒泡了。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/d4t48seReH2OJZwgAGx4fg