冒泡排序是一種通過交換元素位置實現(xiàn)的穩(wěn)定排序方式，其特點是每一輪排序后茁瘦，都會在首端或尾端產(chǎn)生一個已排序元素，就像水泡不斷上浮一樣遍搞，通過多次排序祥款，最終所有元素變得有序清笨。
算法過程
以遞增排序為例，初始集合即為待排序集合刃跛，已排序集合初始為空
- 從待排序集合中第一個元素開始向后遍歷集合中元素抠艾，比較與下一個元素值的大小，大于下一個元素值則交換兩個元素位置桨昙，直到待排序集合最后一個元素检号；
- 標記待排序集合最后一個元素為已排序；
- 重復(fù)步驟 1,2蛙酪，直到待排序集合只有一個元素
演示示例
初始狀態(tài)：0 次排序
待排序集合：[6,3,4,0,2,1,8,5,9,7]
已排序集合：[]
初始狀態(tài)為：
根據(jù)算法過程：
- 步驟一齐苛，從待排序集合中第一個元素開始，比較 6 和 3桂塞，比較大小并交換位置后凹蜂，選擇第二個元素，比較 6 和 4阁危，比較大小并交換位置玛痊，依次遍歷直到待排序集合最后一個元素；
- 步驟二狂打，標記待排序集合中的最后一個元素為已排序擂煞，即元素 9 標記為已排序，從待排序集合中移除該元素
1 次排序后
待排序集合：[3, 4, 0, 2, 1, 6, 5, 8, 7]
已排序集合：[9]
根據(jù)算法過程步驟三趴乡，待排序集合中不止一個元素对省，所以重復(fù)執(zhí)行步驟一、二：
- 步驟一浙宜，遍歷待排序集合官辽，選擇第一個元素，比較 3,4粟瞬，比較大小后，選擇第二個元素萤捆，比較 4,0裙品，比較大小并交換位置俗批，選擇第三個元素，比較4,2市怎，依次遍歷直到集合最后一個元素岁忘；
- 步驟二，標記最后一個元素為已排序
2 次排序后
待排序集合：[3, 0, 2, 1, 4, 5, 6, 7]
已排序集合：[8, 9]
...
...
...
9 次排序后
待排序集合：[0]
已排序集合：[1, 2, 3, 4, 5, 6, 7, 8, 9]
觀察以上過程可知区匠，每次排序后會有一個元素變?yōu)橐雅判蚋上瘢从幸粋€元素處于正確的位置上。所以 個元素的序列驰弄，經(jīng)過
次排序后麻汰，則有
個元素處于已排序狀態(tài)，則剩下的一個元素不再需要進行排序戚篙。
算法示例
def bubbleSort(arr):
for i in range(1, len(arr)): # 迭代次數(shù)
flag = True
for j in range(len(arr) - i): # 遍歷比較每個元素與下一個元素值大小
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
flag = False
if flag:
break
代碼分析 ：
- 以上代碼中五鲫，第一層循環(huán)為需要進行的迭代次數(shù)，元素個數(shù)為
的集合岔擂，最多需要
次迭代即可確定
- 第二層循環(huán)為待排序集合中元素的遍歷比較大小操作乱灵，隨著迭代次數(shù)的增加塑崖，待排序元素個數(shù)減少；
- 代碼中增加了一個 flag 標志變量痛倚，用于標志排序結(jié)束狀態(tài)弃舒。若某一輪迭代中，待排序集合中元素遍歷過程中状原，沒有發(fā)生元素位置交換操作聋呢，則該待排序集合為有序的，排序算法結(jié)束颠区。
算法分析
冒泡排序是一種穩(wěn)定排序算法削锰，排序過程中，如果兩個元素值相等毕莱，則不交換元素位置器贩。對于 個元素的序列：
- 最壞情況下，當(dāng)序列為逆序時朋截，需要
次迭代部服，遍歷的元素個數(shù)為
唆姐，所以最壞情況下，算法的交換復(fù)雜度和比較復(fù)雜度都為
;
- 最好情況下廓八，當(dāng)序列為已排序時奉芦，第一次迭代即可結(jié)束排序過程赵抢，第一次遍歷元素個數(shù)為
，交換復(fù)雜度為 0先巴。
算法執(zhí)行過程中其爵，不需要申請額外的序列空間來保存臨時元素，屬于原地排序方式伸蚯，所以算法的空間復(fù)雜度為 摩渺。
github鏈接：冒泡排序
