快捷導(dǎo)航

詳解python算法之冒泡排序

更新時間：2019年03月05日 09:50:29 作者：failymao

這篇文章主要介紹了詳解python算法之冒泡排序，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

python之冒泡排序

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

這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

算法原理

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

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

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

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

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

算法分析

時間復(fù)雜度

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

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

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

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

代碼實現(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ù) 冒泡排序輸入一個數(shù)組名稱為array 其長度為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 time

def bubble_sort(lst):
  '''冒泡排序'''
  # 第一次循環(huán)
  for n in range(len(lst) - 1, 0, -1): #計算原列表的長度-1,取倒序索引

    for i in range(n):
      if lst[i] > lst[i + 1]:    # 比較最后一個與倒數(shù)第二個數(shù)的值,如果倒數(shù)第二個的值,大于最后一個的值
        temp = lst[i]       # 則將倒數(shù)第二個值賦值給臨時變量temp
        lst[i] = lst[i + 1]    # 替換原列表中倒數(shù)第二個索引的值為最后一個
        lst[i + 1] = temp     # 同時改變原列表中最后一個索引值為倒數(shù)第二個的值
  return lst

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

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