詳解python算法之冒泡排序

python之冒泡排序

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

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

算法原理

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

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

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

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

持續(xù)每次對(duì)越來(lái)越少的元素重復(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ù)組名稱(chēng)為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)要處理的無(wú)序部分
   swap(j,j+1)     //兩兩排序（升序/降序）

python代碼

#-*-coding:utf-8-*-
'''冒泡排序也稱(chēng) bubble sort從小到大排序'''
import time

def 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 lst

if __name__ == "__main__":
  lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
  af_sort=bubble_sort(lst)
  print(af_sort)

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