1. 前言

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

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

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

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

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

本文先從冒泡排序的本質(zhì)說起，不僅是形式上理解，而是要做到本質(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ù)字出來，站在擂臺(tái)上充當(dāng)老大。

老大不是說你想當(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 過程中，大的留在擂臺(tái)上
    if nums[i] > m:
        m = nums[i]
# 最后留在擂臺(tái)上的就是最大值
print("最大值是:", m)

很簡單，對(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ù)列中重新找，不移走，無論找多少次，還會(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(n²)。

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ù)語法，讓找最大值邏輯找完一輪又一輪，外層重復(fù)只要不少于數(shù)列中數(shù)字長度，就能完成排序工作，即使外層重復(fù)大于數(shù)列中數(shù)字長度，只是多做了些無用功而已。

nums = [3, 1, 8, 9, 12, 32, 7]
# 外層重復(fù)的 100 意味著找了 100 次最大值，這里只是說明問題，就是不停找最大值，顯然，是用不著找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ù)列長度減 1 就可以了。5 個(gè)數(shù)字，前面 4 個(gè)找到了，自然大家就都排好序了。

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 個(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(n²)。

3. 選擇排序算法

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

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

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

選擇排序先是假設(shè)第一個(gè)數(shù)字是最小值，然后在后面的數(shù)字里找有沒有比這個(gè)假設(shè)更小的。不是說，找一個(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ì)和冒泡算法還是一樣的，不停找最大（?。┲怠?/p>

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(n²)。

4. 插入排序

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

插入排序的核心思想：

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

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

2.依次從后數(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)：

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

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

后指針用來在后數(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)

后指針用來選擇后數(shù)列中的數(shù)字，前指針用來對(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(n²) 。

5. 快速排序

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

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

類似于畫人物畫。

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

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

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

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

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

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

• 左指針初始指向最左邊數(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í)，第一次二分過程到此結(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)。

6. 總結(jié)

除了冒泡、選擇、插入、快速排序算法，還有很多其它的排序算法，冒泡、選擇 、插入算法很類似，有其相似的比較、交換邏輯?？焖倥判蚴褂昧朔种卫砟?，可從減少時(shí)間復(fù)雜度。

到此這篇關(guān)于詳解Python排序算法的實(shí)現(xiàn)(冒泡,選擇,插入,快速)的文章就介紹到這了,更多相關(guān)Python 排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！