Python排序算法之冒泡排序

更新時間：2023年01月07日 10:17:24 作者：一枚大果殼

我們在編寫代碼時，經(jīng)常需要對一些序列做一些排序，排序的方法很多，下面我們講一下常用的冒泡排序法。需要的朋友可以參考下

1. 前言

所謂排序，就是把一個數(shù)據(jù)群體按個體數(shù)據(jù)的特征按從大到小或從小到大的順序存放。

排序在應(yīng)用開發(fā)中很常見，如對商品按價格、人氣、購買數(shù)量……顯示。

初學編程者，剛開始接觸的第一個稍微有點難理解的算法應(yīng)該是排序算法中的冒泡算法。

我初學時，“腦思維”差點繞在 2 個循環(huán)結(jié)構(gòu)的世界里出不來了。當時，老師要求我們死記冒泡的口訣，雖然有點搞笑，但是當時的知識層次只有那么點，口訣也許是最好的一種學習方式。

當知識體系慢慢建全，對于冒泡排序的理解，自然也會從形式到本質(zhì)的理解。

本文先從冒泡排序的本質(zhì)說起，不僅是形式上理解，而是要做到本質(zhì)里的理解。

2. 冒泡排序算法

所謂冒泡排序算法，本質(zhì)就是求最大值、最小值算法。

所以，可以暫時拋開冒泡排序，先從最大值算法聊起。

為了更好理解算法本質(zhì)，在編寫算法時不建議直接使用 Python 中已經(jīng)內(nèi)置的函數(shù)。如 max()、min()……

求最大值，有多種思路，其中最常用的思路有：

擺擂臺法相鄰的兩個數(shù)字比較法

如一個數(shù)列 nums=[3,1,8,9,12,32,7]

2.1 擺擂臺法

算法思想：

找一個擂臺，從數(shù)列中隨機拎一個數(shù)字出來，站在擂臺上充當老大。

老大不是說你想當就能當，要看其它的兄弟服不服。于是，其它的數(shù)字兄弟會一一登上擂臺和擂臺上的數(shù)字比較，原則是大的留下，小的離開。

如果是找最大值，則是大的留下，小的離開。

反之，如果是找最小值，則是小的留下，大的離開。

你方唱罷我登場。最后留在擂臺上的就是真老大了。

nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個數(shù)字登上擂臺
m = nums[0]
# 其它數(shù)字不服氣
for i in range(1, len(nums)):
    # PK 過程中，大的留在擂臺上
    if nums[i] > m:
        m = nums[i]
# 最后留在擂臺上的就是最大值
print("最大值是:", m)

很簡單，對不對，如果，找到一個最大值后，再在余下的數(shù)字中又找最大值，以此類推，結(jié)局會怎樣？

最后可以讓所有數(shù)字都排好序！這就是排序的最本質(zhì)道理，找著找著就排好序了。

在上面的代碼上稍做改動一下，每次找到最大值后存入到另一個列表中。

nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個數(shù)字登上擂臺
ms=[]
for _ in range(len(nums)):
    m = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > m:
            m = nums[i]
   # 依次找到的最大值存入新數(shù)列          
    ms.append(m)
    # 從原數(shù)列中移出找到的最大值，下一輪要在沒有它的數(shù)列中重新找，不移走，無論找多少次，還會是它
    nums.remove(m)
print(ms)
'''
輸出結(jié)果
[32, 12, 9, 8, 7, 3, 1]
'''

我們可以看到原數(shù)列中的數(shù)字全部都排序了。但是上述排序算法不完美：

另開辟了新空間，顯然空間復雜度增加了。原數(shù)列的最大值找到后就刪除了，目的是不干擾余下數(shù)字繼續(xù)查找最大值。當對所有數(shù)字排好序后，原數(shù)列也破壞了。

能不能不開辟新空間，在原數(shù)列里就完成排序？當然可以。

可以找到最大值就向后移！原數(shù)列從邏輯上從右向左縮小。

nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個數(shù)字登上擂臺
nums_len = len(nums)
for _ in range(len(nums)):
    m = nums[0]
    for i in range(1, nums_len):
        if nums[i] > m:
            m = nums[i]
    # 最大值找到，移動最后
    nums.remove(m)
    nums.append(m)
    # 這個很關(guān)鍵，縮小原數(shù)列的結(jié)束位置
    nums_len = nums_len - 1
print(nums)
'''
輸出結(jié)果:
[32, 12, 9, 8, 7, 3, 1]
'''

在原數(shù)列上面，上述代碼同樣完成了排序。

歸根結(jié)底，上述排序的思路就是不停地找最大值呀、找最大值……找到最后一個數(shù)字，大家自然而然就排好序了。

所以算法結(jié)構(gòu)中內(nèi)層循環(huán)是核心找最大值邏輯，而外層就是控制找呀找呀找多少次。

上述排序算法我們也可稱是冒泡排序算法，其時間復雜度=外層循環(huán)次數(shù)X內(nèi)層循環(huán)次數(shù)。如有 n 個數(shù)字，則外層循環(huán) n-1 次，內(nèi)層循環(huán) n-1 次，在大 O 表示法中，常量可以忽視不計，時間復雜度應(yīng)該是 O（n2）。

2.2 相鄰兩個數(shù)字相比較

如果有 7 個數(shù)字，要找到里面的最大值，有一種方案就是每相鄰的兩個數(shù)字之行比較，如果前面的比后面的數(shù)字大，則交換位置，否則位置不動。上體育課的時候，老師排隊用的就是這種方式，高的和矮的交換位置，一直到不能交換為此。

nums = [3, 1, 8, 9, 12, 32, 7]
for i in range(len(nums)-1):
    # 相鄰 2 個數(shù)字比較
    if nums[i] > nums[i + 1]:
        # 如果前面的數(shù)字大于后面的數(shù)字，則交換
        nums[i], nums[i + 1] = nums[i + 1], nums[i]
# 顯然，數(shù)列最后位置的數(shù)字是最大的
print(nums[len(nums) - 1])
'''
輸出結(jié)果
32
'''

上述代碼同樣實現(xiàn)了找最大值。

和前面的思路一樣，如果找了第一個最大值后，又繼續(xù)在剩下的數(shù)字中找最大值，不停地找呀找，會發(fā)現(xiàn)最后所有數(shù)字都排好序了。

在上述找最大值的邏輯基礎(chǔ)之上，再在外面嵌套一個重復語法，讓找最大值邏輯找完一輪又一輪，外層重復只要不少于數(shù)列中數(shù)字長度，就能完成排序工作，即使外層重復大于數(shù)列中數(shù)字長度，只是多做了些無用功而已。

nums = [3, 1, 8, 9, 12, 32, 7]
# 外層重復的 100 意味著找了 100 次最大值，這里只是說明問題，就是不停找最大值，顯然，是用不著找100 次的
for j in range(100):
    for i in range(len(nums)-1):
        # 相鄰 2 個數(shù)字比較
        if nums[i] > nums[i + 1]:
            # 如果前面的數(shù)字大于后面的數(shù)字，則交換
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

print(nums)

上面的代碼就是冒泡排序算法實現(xiàn)。其實冒泡排序就是找了一輪最大值，又繼續(xù)找最大值的思路。可以對上述算法進行一些優(yōu)化，如已經(jīng)找到的最大值沒有必要再參與后繼的找最大值中去。

顯然，找最大值的最多輪數(shù)是數(shù)列長度減 1 就可以了。5 個數(shù)字，前面 4 個找到了，自然大家就都排好序了。

nums = [3, 1, 8, 9, 12, 32, 7]
# 找多少次最大值，數(shù)列長度減 1
for j in range(len(nums)-1):
    
    for i in range(len(nums)-1-j):
        # 相鄰 2 個數(shù)字比較
        if nums[i] > nums[i + 1]:
            # 如果前面的數(shù)字大于后面的數(shù)字，則交換
            nums[i], nums[i + 1] = nums[i + 1], nums[i]


print(nums)

在學習冒泡排序算法時，不要被外層、內(nèi)層循環(huán)結(jié)構(gòu)嚇住，核心是理解求最大值算法。上述冒泡排序算法的時間復雜度也是 O（n2）。

3. 選擇排序算法

**選擇排序算法是冒泡排序的變種，還是在找最大（?。┲邓惴?，**冒泡排序是一路比較一路交換，為什么要這樣，因為不知道數(shù)列中哪一個數(shù)字是最大（小）值，所以只能不停的比較不停的交換。

選擇排序有一個優(yōu)于冒泡的理念，需要交換時才交換。

所以選擇排序算法的問題就是什么時候需要交換？

選擇排序先是假設(shè)第一個數(shù)字是最小值，然后在后面的數(shù)字里找有沒有比這個假設(shè)更小的。不是說，找一個小的就交換，因為有可能還有比之更小的，只有當后續(xù)所有數(shù)字找完后，再確定進行交換，

還是使用擂擂臺算法實現(xiàn)找最大（?。┲担业胶蠼粨Q位置。

nums = [6, 2, 5, 9, 12, 1, 7]
# 擂臺！假充第一 個數(shù)字是最小值
mi = nums[0]
# 假設(shè)的最小數(shù)字位置
mi_idx = 0
# 真正最小數(shù)字的位置
real_idx = mi_idx
for i in range(mi_idx + 1, len(nums)):
    if nums[i] < mi:
        mi = nums[i]
        # 記住更小數(shù)字的位置，不記著交換
        real_idx = i
# 如有更小的
if real_idx != mi_idx:
    # 交換
    nums[real_idx], nums[mi_idx] = nums[mi_idx], nums[real_idx]
print(nums)
'''
輸出結(jié)果
[1, 2, 5, 9, 12, 6, 7]
'''

以上代碼就是選擇排序的核心邏輯，實現(xiàn)了把最小的數(shù)字移動最前面。

再在上述邏輯基礎(chǔ)上，繼續(xù)在后續(xù)數(shù)字中找出最小值，并移動前面。多找?guī)状尉涂梢粤?！本質(zhì)和冒泡算法還是一樣的，不停找最大（小）值。

nums = [6, 2, 5, 9, 12, 1, 7]
for j in range(len(nums)-1):
    mi = nums[j]
    # 假設(shè)的最小數(shù)字位置
    mi_idx = j
    # 真正最小數(shù)字的位置
    real_idx = mi_idx
    for i in range(mi_idx + 1, len(nums)):
        if nums[i] < mi:
            mi = nums[i]
            # 記住更小數(shù)字的位置
            real_idx = i
    # 如有更小的
    if real_idx != mi_idx:
        # 交換
        nums[real_idx], nums[mi_idx] = nums[mi_idx], nums[real_idx]
print(nums)
'''
輸出結(jié)果:
[1, 2, 5, 6, 7, 9, 12]
'''

選擇排序的時間復雜度和冒泡排序的一樣 O（n2）。

4. 插入排序

打牌的時候，我們剛拿到手上的牌是無序的，在整理紙牌并讓紙牌一步一步變得的有序的過程就是插入算法的思路。

插入排序的核心思想：

把原數(shù)列從邏輯(根據(jù)起始位置和結(jié)束位置在原數(shù)列上劃分)上分成前、后兩個數(shù)列，前面的數(shù)列是有序的，后面的數(shù)列是無序的。

剛開始時，前面的數(shù)列（后面簡稱前數(shù)列）只有唯一的一個數(shù)字，即原數(shù)列的第一個數(shù)字。顯然是排序的！

依次從后數(shù)列中逐個拿出數(shù)字，與前數(shù)列的數(shù)字進行比較，保證插入到前數(shù)列后，整個前數(shù)列還是有序的。

如上，從后數(shù)列中拿到數(shù)字 1 ，然后與前數(shù)字的 3 進行比較，如果是從大到小排序，則 1 就直接排到 3 后面，如果是從小到大排序，則 1 排到 3 前面。

這里，按從小到大排序。

從如上描述可知，插入排序核心邏輯是：

比較：后數(shù)列的數(shù)字要與前數(shù)字的數(shù)字進行大小比較，這個與冒泡和選擇排序沒什么不一樣。移位：如果前數(shù)列的數(shù)字大于后數(shù)列的數(shù)字，則需要向后移位。也可以和冒泡排序一樣交換。插入：為后數(shù)列的數(shù)字在前數(shù)列中找到適當位置后，插入此數(shù)據(jù)。

插入排序的代碼實現(xiàn)：

這里使用前指針和后指針的方案。

前指針用來在前數(shù)列中定位數(shù)字，方向是從右向左。

后指針用來在后數(shù)字中定位數(shù)字，方向是從左向右。

前指針初始的位置之前為前數(shù)列，后指針初始時的位置為后數(shù)列。

nums = [3, 1, 8, 9, 12, 32, 7]

# 后指針指向原數(shù)列的第 2 個數(shù)字,所以索引號從 1 開始
for back_idx in range(1, len(nums)):
    # 前指針和后指針的關(guān)系，
    front_idx = back_idx - 1

    # 臨時變量，比較時，前數(shù)列的數(shù)字有可能要向后移位，需要把后指針指向的數(shù)字提前保存
    tmp = nums[back_idx]

    # 與前數(shù)列中的數(shù)字比較
    while front_idx >= 0 and tmp < nums[front_idx]:
        # 移位
        nums[front_idx + 1] = nums[front_idx]
        front_idx -= 1
    if front_idx != back_idx - 1:
        # 插入
        nums[front_idx + 1] = tmp

print(nums)
'''
輸出結(jié)果
[1,3,7,8,9,12,32]
'''

上述代碼用到了移位和插入操作，也可以使用交換操作。如果是交換操作，則初始時，前、后指針可以指向同一個位置。

nums = [3, 1, 8, 9, 12, 32, 7]
for back_idx in range(1, len(nums)):
    for front_idx in range(back_idx, 0, -1):
        if nums[front_idx] < nums[front_idx - 1]:
            nums[front_idx], nums[front_idx - 1] = nums[front_idx - 1], nums[front_idx]
        else:
            break
print(nums)

后指針用來選擇后數(shù)列中的數(shù)字，前指針用來對前數(shù)列相鄰數(shù)字進行比較、交換。和冒泡排序一樣。

這里有一個比冒泡排序優(yōu)化的地方，冒泡排序需要對數(shù)列中所有相鄰兩個數(shù)字進行比較，不考慮是不是有必要比較。

但插入不一樣，因插入是假設(shè)前面的數(shù)列是有序的，所以如果后指針指向的數(shù)字比前數(shù)列的最后一個數(shù)字都大，顯然，是不需要再比較下去，如下的數(shù)字 `` 是不需要和前面的數(shù)字進行比較，直接放到前數(shù)列的尾部。

插入排序的時間復雜度還是 O(n2) 。

5. 快速排序

快速排序是一個很有意思的排序算法，快速排序的核心思想：

分治思想：全局到局部、或說是粗糙到完美的逐步細化過程。

類似于畫人物畫。

先繪制一個輪廓圖，讓其看起來像什么！

然后逐步細化，讓它真的就是什么！

快速排序也是這個思想，剛開始，讓數(shù)列粗看起來有序，通過逐步迭代，讓其真正有序。

二分思想：在數(shù)列選擇一個數(shù)字（基數(shù)）為參考中心，數(shù)列比基數(shù)大的，放在左邊（右邊），比基數(shù)小的，放在右邊（左邊）。

第一次的二分后：整個數(shù)列在基數(shù)之上有了有序的輪廓，然后在對基數(shù)前部分和后部分的數(shù)字繼續(xù)完成二分操作。

這里使用左、右指針方式描述快速排序：

左指針初始指向最左邊數(shù)字。右指針初始指向最右邊數(shù)字。

這里選擇 8 作為第一次二分的基數(shù)，基數(shù)的選擇沒有特定要求，只要是數(shù)列中的數(shù)字，別客氣，任意選擇。這里把比 8 小的移到 8 的左邊，比 8 大的移動 8 的右邊。

移位的流程：

左指針不停向右移動，至到遇到大于等于基數(shù)的數(shù)字，同理右指針不停向左移動，至到碰到小于等于基數(shù)的數(shù)字。交換左指針和右指針的位置的數(shù)據(jù)。

如上圖，左指針最后會停止在數(shù)字 8 所在位置，右指針會停在數(shù)字 7 所在位置。

交換左、右指針位置的數(shù)字。

依此類推，繼續(xù)移動指針、交換。

第一次二分后，整個數(shù)列會變成如下圖所示：

當左、右指針重合在一起時，第一次二分過程到此結(jié)束。以基數(shù) 8 為分界線，把原數(shù)列分成前、后兩部分，繼續(xù)在前、后數(shù)列上面使用如上二分思想。顯然，使用遞歸是最直接有效的選擇。

如下第一次二分代碼：

nums = [3, 1, 8, 32, 2, 9, 7]

def quick_sort(nums):
    # 左指針
    left = 0
    # 右指針
    right = len(nums) - 1
    # 基數(shù)，可以是任意數(shù)字，一般選擇數(shù)列的第一個數(shù)字
    base_n = 8
    while left < right:
        # 左指針向右移動，至到時左指針位置數(shù)字大于等于基數(shù)，
        while nums[left] < base_n and left < right:
            left += 1
        while nums[right] > base_n and right > left:
            right -= 1
        # 交換
        nums[left], nums[right] = nums[right], nums[left]

quick_sort(nums)
print(nums)

輸出結(jié)果：

[3, 1, 7, 2, 8, 9, 32]

和上面的演示流程圖的結(jié)果一樣。

使用遞歸進行多次二分：

nums = [3, 1, 8, 32, 2, 9, 7]

def quick_sort(nums, start, end):
    if start >= end:
        return
    # 左指針
    left = start
    # 右指針
    right = end
    # 基數(shù)
    base_n = nums[start]
    while left < right:
        while nums[right] > base_n and right > left:
            right -= 1
        # 左指針向右移動，至到時左指針位置數(shù)字大于等于基數(shù)，
        while nums[left] < base_n and left < right:
            left += 1
        # 交換
        nums[left], nums[right] = nums[right], nums[left]
    # 左邊數(shù)列
    quick_sort(nums, start, left - 1)
    # 右邊數(shù)列
    quick_sort(nums, right + 1, end)

quick_sort(nums, 0, len(nums) - 1)
print(nums)
'''
輸出結(jié)果
[1, 2, 3, 7, 8, 9, 32]
'''

快速排序的時間復雜度為 O(nlogn)，空間復雜度為O(nlogn)。