# 冒泡排序
## 示意圖
## 運作步驟
1. 比較相鄰的元素，如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。
3. 針對所有的元素重復以上的步驟，除了最后一個。
4. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
## 助記碼
```
i∈[0,N-1) //循環N-1遍
j∈[0,N-1-i) //每遍循環要處理的無序部分
swap(j,j+1) //兩兩排序（升序/降序）
```
## 算法分析
* 最壞時間復雜度 O(n^2)
* 最優時間復雜度 O(n)
* 平均時間復雜度 O(n^2)
## 實現
```Python
def bubble_sort(list=[]):
'''Python中的冒泡排序算法實現
:param list: 需要排序的數字列表
:return: 排序結果
'''
list_len = len(list)
for i in range(list_len - 1): # 剩一個元素時不需要再比較
swap = False # 記錄是否
for j in range(list_len - 1 - i): # 每次都需要兩兩對比前面未排序完成的元素
if list[j + 1] < list[j]: # 比較相鄰元素
list[j], list[j + 1], swap = list[j + 1], list[j], True # 根據大小調換元素位置
if not swap: break # 如果內循環沒有大小交換，則代表已排序完成，不必再往下進行
return list
```
## 測試
```
$ python bubble_sort.py
冒泡排序>>>
請輸入需要排序的數字，用英文半角逗號隔開，直接回車則使用默認數據：
需要排序的數字為：
8,-5,10,6,-23,15,45
排序結果：
-23,-5,6,8,10,15,45
```
# 代碼庫地址
[https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)
