python之冒泡排序

概念: 重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯(cuò)誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素已經(jīng)排序完成

這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”。

算法原理

冒泡排序算法的原理如下：

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

算法分析

時(shí)間復(fù)雜度

若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)

 和記錄移動(dòng)次數(shù) 均達(dá)到最小值： ， 。

所以，冒泡排序最好的時(shí)間復(fù)雜度為 。

冒泡排序的最壞時(shí)間復(fù)雜度為

代碼實(shí)現(xiàn)

偽代碼

function bubble_sort (array, length) {  var i, j;  for(i from 1 to length-1){    for(j from 0 to length-1-i){      if (array[j] > array[j+1])        swap(array[j], array[j+1])    }  }}

偽代碼解釋

函數(shù) 冒泡排序 輸入 一個(gè)數(shù)組名稱為array 其長(zhǎng)度為length 
    i 從 1 到 (length - 1) 
        j 從 0 到 (length - 1 - i) 
            如果 array[j] > array[j + 1] 
                交換 array[j] 和 array[j + 1] 的值 
            如果結(jié)束 
        j循環(huán)結(jié)束 
    i循環(huán)結(jié)束 
函數(shù)結(jié)束

助記碼

 i∈[0,N-1)        //循環(huán)N-1遍  j∈[0,N-1-i)      //每遍循環(huán)要處理的無序部分   swap(j,j+1)     //兩兩排序（升序/降序）

python代碼

#-*-coding:utf-8-*-'''冒泡排序也稱 bubble sort從小到大排序'''import timedef bubble_sort(lst):  '''冒泡排序'''  # 第一次循環(huán)  for n in range(len(lst) - 1, 0, -1): #計(jì)算原列表的長(zhǎng)度-1,取倒序索引    for i in range(n):      if lst[i] > lst[i + 1]:    # 比較最后一個(gè)與倒數(shù)第二個(gè)數(shù)的值,如果倒數(shù)第二個(gè)的值,大于最后一個(gè)的值        temp = lst[i]       # 則將倒數(shù)第二個(gè)值賦值給臨時(shí)變量temp        lst[i] = lst[i + 1]    # 替換原列表中倒數(shù)第二個(gè)索引的值為最后一個(gè)        lst[i + 1] = temp     # 同時(shí)改變?cè)斜碇凶詈笠粋€(gè)索引值為倒數(shù)第二個(gè)的值  return lstif __name__ == "__main__":  lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]  af_sort=bubble_sort(lst)  print(af_sort)

總結(jié)冒泡排序的實(shí)現(xiàn)（類似下面）通常會(huì)對(duì)已經(jīng)排序好的數(shù)列拙劣地運(yùn)行（），而插入排序在這個(gè)例子只需要個(gè)運(yùn)算。算法的核心知識(shí)點(diǎn)是: 循環(huán)比較, 交叉換位!