什么是冒泡排序？冒泡排序算法的實(shí)現(xiàn)過程

冒泡排序?qū)崿F(xiàn)原理

冒泡排序(Bubble Sort)是一種很原始的排序方法，就是通過不斷地交換“大數(shù)”的位置達(dá)到排序的目的。因?yàn)椴粩喑霈F(xiàn)“大數(shù)”類似于水泡不斷出現(xiàn)，因此被形象地稱為冒泡算法。

冒泡算法的基本原理：比較相鄰兩個(gè)數(shù)字的大小。將兩數(shù)中比較大的那個(gè)數(shù)交換到靠后的位置。

不斷地交換下去就可以將最大的那個(gè)數(shù)放到隊(duì)列的尾部。然后重頭再次交換，直到將數(shù)列排成有序數(shù)列。接下來我們以以數(shù)列[5, 9, 3, 1, 2, 8, 4, 7, 6]為例，演示冒泡排序的實(shí)現(xiàn)過程，最初的數(shù)列順序如下圖所示：

第一輪排序：按照冒泡排序的原理，比較相鄰兩個(gè)數(shù)字的大小。從數(shù)列末端開始，第1次比較7和6的大小。7>6，交換7和6的位置。把較大的那個(gè)數(shù)7交換到靠后的位置。

第2次排序比較4和6的大小。6比4大，不需要交換位置。第3次排序比較8和4的大小。4比8小，交換4和8的位置位置。

第4次排序比較2和4的大小。4比2大，不需要交換位置。第5次排序比較2和1的大小。2比1大，不需要交換位置。

第6次排序比較1和3的大小。1比3小，交換1和3的位置。第7次排序比較1和9的大小。1比9小，交換1和9的位置。

第8次排序比較1和5的大小。1比5小，交換1和5的位置。

第一輪排序結(jié)束, 成功的將序列中最小的數(shù)1交換到了隊(duì)列最前面。

第二輪排序：過程與前一輪類似，依然從末尾開始進(jìn)行相鄰兩個(gè)元素的比較當(dāng)前面的元素比后面的元素大，交換兩個(gè)元素的位置，第二輪排序只需要進(jìn)行7次比較

經(jīng)過第二輪排序后，數(shù)列中最小的兩個(gè)元素已經(jīng)交換到數(shù)列的最前面。

第三輪排序：依舊是回到數(shù)列的末尾，重新比較相鄰的兩個(gè)元素。

經(jīng)過六次比較后，第三輪排序完成， 1,2,3三個(gè)最小的元素移動(dòng)到了數(shù)列的頭部。

第四輪排序：經(jīng)過五次比較，第四輪排序完成后，1,2,3,4四個(gè)最小的元素移動(dòng)到了數(shù)列的頭部。

完整的排序過程需要經(jīng)過八輪比較(9個(gè)元素)，后四輪的排序過程與前面類似，經(jīng)過八輪排序后，排序過程完成。

一個(gè)n個(gè)數(shù)的數(shù)列需要排序n-1輪。這樣可以確保得到一個(gè)有序的數(shù)列。因此冒泡排序的時(shí)間復(fù)雜度是O(n² )。

冒泡排序代碼

在寫冒泡排序的代碼前，先編寫一段程序，創(chuàng)建無序數(shù)列，用于測試排序算法。創(chuàng)建無序數(shù)列的程序randomList.py，代碼如下：

import random

def getrandomlist(n):
    '''返回一個(gè)長度為n的整數(shù)列表，數(shù)據(jù)范圍[0,1000) '''
    tlist = []
    for i in range(n):
        tlist.append(random.randrange(1000))
    return tlist

if __name__ == "__main__":
    tlist = getrandomlist(10)
    print(tlist)

冒泡排序的程序bubbleSort.py的代碼如下：

def bubblesort(tlist):
    '''冒泡排序 '''
    if len(tlist) <= 1:
        return tlist
    for i in range(1, len(tlist)): # 一共進(jìn)行n-1輪比較(交換)
        for j in range(len(tlist)-1, i-1, -1): # 從列表末尾開始比較,每比較一輪減少一個(gè)元素
            if tlist[j-1] >= tlist[j]: #比較相鄰兩數(shù)的大小
                tlist[j-1], tlist[j] = tlist[j], tlist[j-1] #將大數(shù)交換到靠后的位置
    return tlist

def bubblesort(tlist):
    '''冒泡排序 '''
    if len(tlist) <= 1:
        return tlist
    for i in range(1, len(tlist)): # 一共進(jìn)行n-1輪比較(交換)
        for j in range(len(tlist)-1, i-1, -1): # 從最后開始比較,每輪比較結(jié)束減少一個(gè)元素
            if tlist[j-1] >= tlist[j]: #比較相鄰兩數(shù)的大小
                tlist[j-1], tlist[j] = tlist[j], tlist[j-1] #將大數(shù)交換到靠后的位置
    return tlist
if __name__ == "__main__":
    list_ = getrandomlist(10) # 獲取隨機(jī)大小的10個(gè)元素
    print(list_) # 打印
    print(bubblesort(list_)) # 打印 排序結(jié)果