冒泡排序是是一種比較基礎(chǔ)簡單的算法。
它的原理是通過對比前后的元素大小俩垃，將較大的數(shù)換到后面的方式來實(shí)現(xiàn)排序 。
排序過程
舉個(gè)例子：
假如現(xiàn)在有一個(gè)無序數(shù)組disorder_arr = [4,2,19,10,-1]。
第一步：
取第0個(gè)元素4因苹，和第1個(gè)元素2
對比鞭呕，發(fā)現(xiàn)4比2大蛤育。
第二步：
交換4與2的索引。
即第0個(gè)元素為2,第1個(gè)元素為4葫松，disorder_arr =[2,4,19,10,-1]
第三步：
取第1個(gè)元素4瓦糕，和第2個(gè)元素19
對比，發(fā)現(xiàn)4小于19腋么。
第四步：
保持索引不變咕娄。
重復(fù)上面步驟
遍歷n-1次數(shù)組，會將數(shù)組中最大的數(shù)換到數(shù)組最后面的位置珊擂。
然后重頭開始遍歷圣勒，遍歷n-2次數(shù)組。
為什么是n-2次呢摧扇？
因?yàn)樽畲蟮臄?shù)已經(jīng)在最后了圣贸，不需要再判斷多一次了，
所以是n-2次扛稽。
這次會將第二大的數(shù)放置在倒數(shù)第二個(gè)索引上吁峻。
寫一段代碼
代碼依然是使用Python3實(shí)現(xiàn)的
普通實(shí)現(xiàn)
通常所見到的冒泡排序都是這種實(shí)現(xiàn)，用了兩層循環(huán)庇绽。
時(shí)間復(fù)雜度為O(n^2)
def bubble(self, disorder_arr: list):
for i in range(len(disorder_arr)): # 遍歷n次數(shù)組
for j in range(len(disorder_arr) - i - 1): # 遍歷n-i-1個(gè)數(shù)組的元素
if disorder_arr[j] > disorder_arr[j + 1]: # 對比當(dāng)前數(shù)與下一個(gè)數(shù)
temp = disorder_arr[j]
disorder_arr[j] = disorder_arr[j + 1]
disorder_arr[j + 1] = temp
return disorder_arr
一個(gè)for的實(shí)現(xiàn)
還有一個(gè)比較特別的實(shí)現(xiàn)锡搜，只用了一層循環(huán)
def bubble2(self, disorder_arr: list):
team = len(disorder_arr) - 1
i = 0
while i < team: # 遍歷n-1個(gè)元素，直到team等于i瞧掺，即team=0
if disorder_arr[i] > disorder_arr[i + 1]: # 對比當(dāng)前數(shù)與下一個(gè)數(shù)
temp = disorder_arr[i]
disorder_arr[i] = disorder_arr[i + 1]
disorder_arr[i + 1] = temp
if i == team - 1: # 如果遍歷到了最后一個(gè)元素耕餐，則重置i的值，并給team減1
i = -1
team -= 1
i += 1
return disorder_arr
乍一看辟狈，感覺時(shí)間復(fù)雜度是O(n)
但玄機(jī)在于循環(huán)下面的if i == team - 1:這個(gè)判斷肠缔，
當(dāng)遍歷到數(shù)組末尾的時(shí)候，會將i的值重置哼转，
因此這個(gè)實(shí)現(xiàn)的時(shí)間復(fù)雜度依然是O(n^2)
分析
在冒泡排序中明未，首先需要遍歷n-1次數(shù)組，然后要執(zhí)行n次這種操作壹蔓。
因此它的時(shí)間復(fù)雜度為O(n^2)
那么它是一個(gè)穩(wěn)定的算法嗎趟妥？
如果進(jìn)行比較的時(shí)候，兩個(gè)數(shù)相等佣蓉，那么算法將不會對他們進(jìn)行交換索引披摄，
因此它是穩(wěn)定的亲雪。
以上代碼已上傳至[github][https://github.com/alisen39/algorithm/blob/master/algorithms/sorting/bubbleSort.py]
歡迎大家友好交流[握手]
