冒泡排序
冒泡排序就是重復“從序列右邊開始比較相鄰兩個數(shù)字的大小叹谁，再根據(jù)結果交換兩個數(shù)字
的位置”這一操作的算法矢腻。在這個過程中瓶殃，數(shù)字會像泡泡一樣敲茄，慢慢從右往左“浮”到序列的
頂端位谋，所以這個算法才被稱為“冒泡排序”。
- 比較相鄰元素堰燎， 如果第一個比第二個大掏父， 就交換他們兩個
- 對每一對相鄰的元素做同樣的工作， 執(zhí)行完畢后秆剪， 找到第一個最大值
- 重復以上步驟赊淑， 每次比較 次數(shù) - 1， 直到不需要比較
image
image
image
image
image
image
image
image
在冒泡排序中仅讽，第 1 輪需要比較 n -1 次陶缺，第 2 輪需要比較 n -2 次……第 n -1 輪需
要比較 1 次。因此洁灵，總的比較次數(shù)為 (n -1) +(n -2) +…+1 ≈ n^2
/2饱岸。這個比較次數(shù)恒定為該數(shù)值，和輸入數(shù)據(jù)的排列順序無關处渣。
不過伶贰，交換數(shù)字的次數(shù)和輸入數(shù)據(jù)的排列順序有關。假設出現(xiàn)某種極端情況罐栈，如輸
入數(shù)據(jù)正好以從小到大的順序排列黍衙，那么便不需要任何交換操作；反過來荠诬，輸入數(shù)據(jù)要
是以從大到小的順序排列琅翻，那么每次比較數(shù)字后便都要進行交換位仁。因此，冒泡排序的時
間復雜度為 O(n^2)方椎。
一層循環(huán)/右側開始版
arr = [5, 9, 3, 1, 2, 8, 4, 7, 6]
def BubbleSort(arr:list)->list:
num = 0
for i in range(0, len(arr)-1):
for j in range(len(arr) - 1, i, -1):
num +=1
if arr[j - 1] > arr[j]:
arr[j - 1], arr[j] = arr[j], arr[j - 1]
print(num)
return arr
print(BubbleSort(arr))
