<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Bubble Sort - 冒泡排序 -------- #### 問題 用冒泡排序對長度為$$ n $$的無序序列$$ s $$進行排序。 #### 解法 本問題對無序序列$$ s $$升序排序，排序后$$ s $$是從小到大的。 將長度為$$ n $$的序列$$ s $$分為$$ left $$和$$ right $$兩個部分，其中$$ left $$是無序部分，范圍為$$ s[0,k] $$，$$ right $$是有序部分，范圍為$$ s[k+1,n-1] $$，其中$$ 0 \lt k \le n $$。初始時$$ left $$范圍為$$ s[0,n-1] $$，$$ right $$為空。 $$ left $$從左邊第一個元素$$ s[i] $$（初始時$$ i = 0 $$）開始向右遍歷，依次對$$ s[i] $$和$$ s[i+1] $$進行比較，若$$ s[i] \gt s[i+1] $$則交換兩個元素，直到$$ i = k $$為止，完成一次遍歷操作。每次遍歷會將$$ left $$中的最大元素移動到$$ s[0,k] $$的最右邊，之后就可以將$$ left $$的范圍縮小為$$ s[0,k-1] $$，$$ right $$的范圍擴大為$$ s[k,n-1] $$。 例如對于下圖中的數組$$ s $$，$$ left $$為$$ s[0,5] $$，$$ right $$為$$ s[6,n-1] $$。從$$ i = 0 $$開始向右遍歷，依次比較$$ s[i] $$和$$ s[i+1] $$，若$$ s[i] \gt s[i+1] $$則交換兩個元素，直到$$ i = 5 $$。    $$ \cdots \cdots $$  然后將$$ left $$中的最大值$$ s[5] = 57 $$合并到$$ right $$部分中，再進行新一輪的遍歷交換操作。  重復上面的遍歷交換操作，從$$ i = 0 $$開始向右遍歷。這樣直到$$ left $$部分為空，$$ right $$部分即為已序數組，算法結束。對于長度為$$ n $$的序列$$ s $$，每一輪將$$ left $$中的最大值移動到$$ right $$，時間復雜度為$$ O(n) $$，總共需要$$ n $$輪，該算法的時間復雜度為$$ O(n^2) $$。 -------- #### 源碼 [BubbleSort.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/BubbleSort.h) [BubbleSort.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/BubbleSort.cpp) #### 測試 [BubbleSortTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/BubbleSortTest.cpp)