欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實(shí)現(xiàn)冒泡排序算法的示例解析

 更新時(shí)間:2022年06月07日 10:56:49   作者:小袁ITSuper  
冒泡排序(Bubble Sort)是一種簡單的排序算法。本文將詳細(xì)為大家講講Python實(shí)現(xiàn)冒泡排序算法的方法,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下

1. 算法描述

冒泡排序(Bubble Sort)是一種簡單的排序算法。它重復(fù)地遍歷要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過來。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

2. 算法分析

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

2. 對每一對相鄰元素作同樣的工作,從開始第一對到結(jié)尾的最后一對。這步做完后,最后的元素會(huì)是最大的數(shù)。

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

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

那么我們需要進(jìn)行n-1次冒泡過程,每次對應(yīng)的比較次數(shù)如下圖所示:

3. 動(dòng)圖展示

看明白了運(yùn)行流程,我們再來看看動(dòng)圖實(shí)現(xiàn):

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

我們對如下無序列表進(jìn)行排序

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

import time

pop_list = [19, 14, 10, 4, 15, 26, 20, 96]
print("沒排序前的列表為:", pop_list)
# 記錄開始時(shí)間
start = time.time()
# 外層循環(huán)控制輪數(shù)
for i in range(len(pop_list) - 1):
    # 內(nèi)層循環(huán)控制比較次數(shù)
    for j in range(len(pop_list) - i - 1):
        # 如果前一個(gè)數(shù)字比后一個(gè)數(shù)字大,就交換位置
        if pop_list[j] > pop_list[j + 1]:
            # python特有交換位置方式
            pop_list[j], pop_list[j + 1] = pop_list[j + 1], pop_list[j]

print("排序好的列表為:", pop_list)
# 記錄結(jié)束時(shí)間
end = time.time()
print("算法總耗時(shí):", end - start)

運(yùn)行結(jié)果:

5. 算法升級

在循環(huán)中定義了一個(gè)變量count,如果第一次循環(huán)后count沒有變化,就說明輸入的是有序序列,這時(shí)我們直接return退出循環(huán),這時(shí)候的時(shí)間復(fù)雜度為O(n)

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

import time

def bubble_sort(pop_list):
    for j in range(len(pop_list) - 1, 0, -1):
        count = 0
        for i in range(0, j):
            if pop_list[i] > pop_list[i + 1]:
                pop_list[i], pop_list[i + 1] = pop_list[i + 1], pop_list[i]
                count += 1
        if count == 0:
            return


pop_list = [19, 14, 10, 4, 15, 26, 20, 96]
print("沒排序前的列表為:", pop_list)
# 記錄開始時(shí)間
start = time.time()
bubble_sort(pop_list)
print("排序好的列表為:", pop_list)
# 記錄結(jié)束時(shí)間
end = time.time()
print("算法總耗時(shí):", end - start)

運(yùn)行結(jié)果:

6. 時(shí)間復(fù)雜度分析

最優(yōu)時(shí)間復(fù)雜度:O(n) (表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素,排序結(jié)束。)

最壞時(shí)間復(fù)雜度:O(n^2)

穩(wěn)定性:穩(wěn)定

排序分析:待排數(shù)組中一共有8個(gè)數(shù),第一輪排序時(shí)進(jìn)行了7次比較,第二輪排序時(shí)進(jìn)行了6比較,依次類推,最后一輪進(jìn)行了1次比較。

數(shù)組元素總數(shù)為N時(shí),則一共需要的比較次數(shù)為:(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2

算法約做了N^2/2次比較。因?yàn)橹挥性谇懊娴脑乇群竺娴脑卮髸r(shí)才交換數(shù)據(jù),所以交換的次數(shù)少于比較的次數(shù)。如果數(shù)據(jù)是隨機(jī)的,大概有一半數(shù)據(jù)需要交換,則交換的次數(shù)為N^2/4(不過在最壞情況下,即初始數(shù)據(jù)逆序時(shí),每次比較都需要交換)。

交換和比較的操作次數(shù)都與 N^2 成正比,由于在大O表示法中,常數(shù)忽略不計(jì),冒泡排序的時(shí)間復(fù)雜度為O(N^2)。

以上就是Python實(shí)現(xiàn)冒泡排序算法的示例解析的詳細(xì)內(nèi)容,更多關(guān)于Python冒泡排序算法的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 基于Python的身份證號碼自動(dòng)生成程序

    基于Python的身份證號碼自動(dòng)生成程序

    今天收到一個(gè)小需求:需要一個(gè)自動(dòng)生成身份證號碼的小程序。近期用python較多,因此打算用python實(shí)現(xiàn)
    2014-08-08
  • Python中列表索引 A[ : 2 ]與A[ : , 2]的區(qū)別說明

    Python中列表索引 A[ : 2 ]與A[ : ,&nb

    這篇文章主要介紹了Python中列表索引 A[ : 2 ]與A[ : , 2]的區(qū)別說明,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-05-05
  • python調(diào)用java的jar包方法

    python調(diào)用java的jar包方法

    今天小編就為大家分享一篇python調(diào)用java的jar包方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-12-12
  • Python二叉樹初識(新手也秒懂!)

    Python二叉樹初識(新手也秒懂!)

    二叉樹是一種簡單的樹形結(jié)構(gòu),其每個(gè)節(jié)點(diǎn)的分支節(jié)點(diǎn)數(shù)有0,1或2個(gè),下面這篇文章主要給大家介紹了關(guān)于Python二叉樹的相關(guān)資料,本文介紹的非常通俗易懂,新手也秒懂,需要的朋友可以參考下
    2022-05-05
  • Python?Pyperclip模塊安裝和使用詳解

    Python?Pyperclip模塊安裝和使用詳解

    Pyperclip模塊兼容python2和python3,能跨平臺使用,這篇文章主要介紹了Pyperclip模塊安裝和使用詳解,需要的朋友可以參考下
    2023-03-03
  • python使用jieba實(shí)現(xiàn)中文分詞去停用詞方法示例

    python使用jieba實(shí)現(xiàn)中文分詞去停用詞方法示例

    jieba分詞,完全開源,有集成的python庫,簡單易用。下面這篇文章主要給大家介紹了關(guān)于python使用jieba實(shí)現(xiàn)中文分詞去停用詞的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考借鑒,下面來一起看看吧。
    2018-03-03
  • Python3控制路由器——使用requests重啟極路由.py

    Python3控制路由器——使用requests重啟極路由.py

    通過本文給大家介紹Python3控制路由器——使用requests重啟極路由.py的相關(guān)知識,代碼寫了相應(yīng)的注釋,以后再寫成可以方便調(diào)用的模塊,感興趣的朋友一起學(xué)習(xí)吧
    2016-05-05
  • python輸出pdf文檔的實(shí)例

    python輸出pdf文檔的實(shí)例

    今天小編就為大家分享一篇python輸出pdf文檔的實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-02-02
  • Python作用域與名字空間原理詳解

    Python作用域與名字空間原理詳解

    這篇文章主要介紹了python作用域與名字空間原理詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-03-03
  • 解決Python中導(dǎo)入自己寫的類,被劃紅線,但不影響執(zhí)行的問題

    解決Python中導(dǎo)入自己寫的類,被劃紅線,但不影響執(zhí)行的問題

    這篇文章主要介紹了解決Python中導(dǎo)入自己寫的類,被劃紅線,但不影響執(zhí)行的問題,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-07-07

最新評論