01
故事起源
幼兒園放學，小朋友們集合，需要先從低到高排隊，應該怎么排呢？
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)，資料規模較小時可采用，但資料過大時就不建議采用冒泡了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286696.html
標籤：其他
上一篇：F. Omkar and Akmar【游戲，組合，逆元】—— Codeforces Round #724 (Div. 2)