Python排序算法之冒泡排序

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

我們?cè)诰帉懘a時(shí)，經(jīng)常需要對(duì)一些序列做一些排序，排序的方法很多，下面我們講一下常用的冒泡排序法。需要的朋友可以參考下

1. 前言

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

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

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

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

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

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

2. 冒泡排序算法

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

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

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

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

擺擂臺(tái)法相鄰的兩個(gè)數(shù)字比較法

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

2.1 擺擂臺(tái)法

算法思想：

找一個(gè)擂臺(tái)，從數(shù)列中隨機(jī)拎一個(gè)數(shù)字出來(lái)，站在擂臺(tái)上充當(dāng)老大。

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

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

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

你方唱罷我登場(chǎng)。最后留在擂臺(tái)上的就是真老大了。

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

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

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

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

nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個(gè)數(shù)字登上擂臺(tái)
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ù)列中重新找，不移走，無(wú)論找多少次，還會(huì)是它
    nums.remove(m)
print(ms)
'''
輸出結(jié)果
[32, 12, 9, 8, 7, 3, 1]
'''

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

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

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

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

nums = [3, 1, 8, 9, 12, 32, 7]
# 第一個(gè)數(shù)字登上擂臺(tái)
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]
    # 最大值找到，移動(dòng)最后
    nums.remove(m)
    nums.append(m)
    # 這個(gè)很關(guān)鍵，縮小原數(shù)列的結(jié)束位置
    nums_len = nums_len - 1
print(nums)
'''
輸出結(jié)果:
[32, 12, 9, 8, 7, 3, 1]
'''

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

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

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

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

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

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

nums = [3, 1, 8, 9, 12, 32, 7]
for i in range(len(nums)-1):
    # 相鄰 2 個(gè)數(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
'''

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

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

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

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

print(nums)

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

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

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


print(nums)

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

3. 選擇排序算法

**選擇排序算法是冒泡排序的變種，還是在找最大（?。┲邓惴ǎ?*冒泡排序是一路比較一路交換，為什么要這樣，因?yàn)椴恢罃?shù)列中哪一個(gè)數(shù)字是最大（?。┲?，所以只能不停的比較不停的交換。

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

所以選擇排序算法的問(wèn)題就是什么時(shí)候需要交換？

選擇排序先是假設(shè)第一個(gè)數(shù)字是最小值，然后在后面的數(shù)字里找有沒有比這個(gè)假設(shè)更小的。不是說(shuō)，找一個(gè)小的就交換，因?yàn)橛锌赡苓€有比之更小的，只有當(dāng)后續(xù)所有數(shù)字找完后，再確定進(jìn)行交換，

還是使用擂擂臺(tái)算法實(shí)現(xiàn)找最大（小）值，找到后交換位置。

nums = [6, 2, 5, 9, 12, 1, 7]
# 擂臺(tái)！假充第一 個(gè)數(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]
'''

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

再在上述邏輯基礎(chǔ)上，繼續(xù)在后續(xù)數(shù)字中找出最小值，并移動(dòng)前面。多找?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]
'''

選擇排序的時(shí)間復(fù)雜度和冒泡排序的一樣 O（n2）。

4. 插入排序

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

插入排序的核心思想：

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

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

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

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

這里，按從小到大排序。

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

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

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

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

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

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

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

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

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

    # 臨時(shí)變量，比較時(shí)，前數(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]
'''

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

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)

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

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

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

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

5. 快速排序

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

分治思想：全局到局部、或說(shuō)是粗糙到完美的逐步細(xì)化過(guò)程。

類似于畫人物畫。

先繪制一個(gè)輪廓圖，讓其看起來(lái)像什么！

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

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

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

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

這里使用左、右指針?lè)绞矫枋隹焖倥判颍?/p>

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

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

移位的流程：

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

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

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

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

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

當(dāng)左、右指針重合在一起時(shí)，第一次二分過(guò)程到此結(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ù)列的第一個(gè)數(shù)字
    base_n = 8
    while left < right:
        # 左指針向右移動(dòng)，至到時(shí)左指針位置數(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é)果一樣。

使用遞歸進(jìn)行多次二分：

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
        # 左指針向右移動(dòng)，至到時(shí)左指針位置數(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]
'''

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