首頁人工智能技術(shù)資訊正文

冒泡排序的原理是什么?怎樣實現(xiàn)冒泡排序【圖文演示】

更新時間:2022-10-19 來源:黑馬程序員 瀏覽量:

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

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

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

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

冒泡排序

第一輪排序:按照冒泡排序的原理,比較相鄰兩個數(shù)字的大小。從數(shù)列末端開始,第1次比較7和6的大小。7>6,交換7和6的位置。把較大的那個數(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交換到了隊列最前面。

第一輪排序交換位置

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

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

數(shù)列交換

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

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

冒泡排序第四輪排序

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

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

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

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

冒泡排序代碼

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

import random

def getrandomlist(n):
    '''返回一個長度為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): # 從列表末尾開始比較,每比較一輪減少一個元素
            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é)束減少一個元素
            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) # 獲取隨機大小的10個元素
    print(list_) # 打印
    print(bubblesort(list_)) # 打印 排序結(jié)果
分享到:
在線咨詢 我要報名
和我們在線交談!