氣泡排序法本質上也是一種選擇排序法, 它使用 "氣泡" 策略, 讓最大的元素像氣泡一樣冒到最上面, 也就是與陣列最後一個元素進行交換. 不過它並不是像選擇排序法那樣直接進行交換, 而是通過相鄰交換的形式 : 在一次氣泡排序中, 相鄰元素進行比較, 如果左側的元素比右側的元素要大, 那麼進行交換
通過上述描述, 我們可以知道, 一次氣泡排序可以將最大的那個元素通過不斷交換, 最終讓其停頓在陣列的最後一個位置. 而氣泡排序法就是通過這樣不斷地 "冒出氣泡", 讓每一個元素被交換到對應的位置, 最終完成排序
在上面所演示的排序中, 只進行了一次氣泡排序就已經完成了, 這一次是讓陣列的第 1 個元素開始, 尋訪到第 n - 1 個元素, 然後相鄰的元素進行比較和交換. 接下來這一次是從第 1 個元素開始, 尋訪到第 n - 2 個元素. 因為此時第 n 個元素必定是最大的元素
void bubble_sort(int arr[], int size) {
for(auto i {size}; i > 0; --i) {
for(auto j {1}; j < i; ++j) {
if(arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
}
}
}
}
在上面的 SVG 圖像中, 我們已經看出了一個問題 : 即時序列已經有序, 氣泡排序仍然會繼續, 直到所有的迴圈結束, 函式終結. 為了效率考慮, 如果檢測到序列已經有序, 那麼就應該即時終止排序. 因此, 我們仍然使用布林變數來實作. 我們發現, 如果某一個序列已經有序, 那麼不會發生任何交換, 此時就可以判定序列有序 :
void bubble_sort(int arr[], int size) {
bool swapped {true};
for(auto i {size}; i > 0 and swapped; --i) {
swapped = false;
for(auto j {1}; j < i; ++j) {
if(arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
if(not swapped) {
swapped = true;
}
}
}
}
}
最後, 我們來討論氣泡排序的穩定性. 在對比的過程中, 我們發現, 若且唯若後面的元素比前面的元素小的時候, 才會發生交換. 我們簡單地考慮前後兩個元素相同的情況, 此時 arr[j] < arr[j - 1]
條件並不成立, 因此並不發生交換. 所以相同元素之間, 其前後排列並不發生改變. 因此, 氣泡排序法是穩定的
對於泛型的實作方式, 可以參考本人的 GitHub : GitHub 點擊直達, 搜尋 bubble_sort
自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《【演算法】氣泡排序法 (Bubble Sort)》https://jonny.vip/2020/02/02/%e3%80%90%e6%bc%94%e7%ae%97%e6%b3%95%e3%80%91%e6%b0%a3%e6%b3%a1%e6%8e%92%e5%ba%8f%e6%b3%95-bubble-sort/
Leave a Reply