Python 排序算法[一]：令你茅塞頓開，卻又匪夷所思

“

閱讀本文大概需要 9 分鐘。

”

閱讀本文可以幫助你解開以下疑惑：算法是什么？算法難不難？怎么才能夠在短時(shí)間內(nèi)熟悉業(yè)內(nèi)的經(jīng)典算法呢？這些算法用 Python 實(shí)現(xiàn)會(huì)是什么樣的？它們的耗時(shí)會(huì)跟時(shí)間復(fù)雜度相關(guān)嗎？

神馬是算法？

算法中的指令描述的是一個(gè)計(jì)算，當(dāng)其運(yùn)行時(shí)能從一個(gè)初始狀態(tài)和（可能為空的）初始輸入開始，經(jīng)過一系列有限而清晰定義的狀態(tài)，最終產(chǎn)生輸出并停止于一個(gè)終態(tài)。一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移不一定是確定的。隨機(jī)化算法在內(nèi)的一些算法，包含了一些隨機(jī)輸入。

算法的幾大特征

一個(gè)算法應(yīng)該具有 “有窮性”、“確切性”、“輸入項(xiàng)”、“輸出項(xiàng)”、“可行性” 等重要的特征。這些特征對應(yīng)的含義如下：

• 有窮性（Finiteness）--  算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止；

• 確切性 (Definiteness) -- 算法的每一步驟必須有確切的定義；

• 輸入項(xiàng) (Input) -- 一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始情況，所謂0個(gè)輸入是指算法本身定出了初始條件；

• 輸出項(xiàng) (Output) -- 一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；

• 可行性 (Effectiveness) --  算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步，即每個(gè)計(jì)算步都可以在有限時(shí)間內(nèi)完成（也稱之為有效性）。

算法兩大要素

• 一，數(shù)據(jù)對象的運(yùn)算和操作：計(jì)算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的。一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合，成為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。一個(gè)計(jì)算機(jī)的基本運(yùn)算和操作有如下四類：

• 1 算術(shù)運(yùn)算：加減乘除等運(yùn)算

• 2 邏輯運(yùn)算：或、且、非等運(yùn)算

• 3 關(guān)系運(yùn)算：大于、小于、等于、不等于等運(yùn)算

• 4 數(shù)據(jù)傳輸：輸入、輸出、賦值等運(yùn)算 [1]

• 二，算法的控制結(jié)構(gòu)：一個(gè)算法的功能結(jié)構(gòu)不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。

算法的好壞評(píng)定

你說這個(gè)算法好、他卻說這個(gè)算法不好，兩人爭論不休。那么好與不好應(yīng)該怎么評(píng)定呢？

同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。

• 時(shí)間復(fù)雜度 -- 算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。一般來說，計(jì)算機(jī)算法是問題規(guī)模n 的函數(shù)f(n)，算法的時(shí)間復(fù)雜度也因此記做。
  T(n)=Ο(f(n))
  因此，問題的規(guī)模n 越大，算法執(zhí)行的時(shí)間的增長率與f(n) 的增長率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time Complexity）。

• 空間復(fù)雜度 -- 算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。

• 正確性 - 算法的正確性是評(píng)價(jià)一個(gè)算法優(yōu)劣的最重要的標(biāo)準(zhǔn)。

• 可讀性 - 算法的可讀性是指一個(gè)算法可供人們閱讀的容易程度。

• 健壯性 - 健壯性是指一個(gè)算法對不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。

以上的理論知識(shí)可以讓我們對算法有個(gè)大致的理解和認(rèn)知，接下來我們將使用 Python 實(shí)現(xiàn)幾個(gè)經(jīng)典的 排序算法，并在文末對比 Java 的實(shí)現(xiàn)。

算法的內(nèi)外之分

除了《唐門》弟子之外（斗羅大陸中的唐門），排序算法也有內(nèi)外之分。

• 內(nèi)部排序指的是在內(nèi)存中進(jìn)行排序；

• 外部排序指的是由于數(shù)據(jù)量較大，無法讀入內(nèi)存而需要在排序過程中訪問外部存儲(chǔ)的情況；

比較經(jīng)典的排序算法如下圖所示：

有冒泡排序、歸并排序、插入排序、希爾排序、選擇排序、快速排序等。

它們各自的時(shí)間復(fù)雜度如下圖所示：

注意：今天先講冒泡、選擇和插入排序

在開始之前，首先要感謝公眾號(hào)《五分鐘學(xué)算法》的大佬 “程序員小吳” 授權(quán)動(dòng)態(tài)圖片和排序思路。

冒泡排序

冒泡排序的過程如上圖所示，對應(yīng)的算法步驟為：

根據(jù)動(dòng)態(tài)圖和算法步驟， Python 實(shí)現(xiàn)冒泡排序的代碼如下：

data = [5, 4, 8, 3, 2]
def bubble(data):
    for i in range(len(data)-1):    # 排序次數(shù)
        for s in range(len(data)-i-1):  # s為列表下標(biāo)
            if data[s] > data[s+1]:
                data[s], data[s+1] = data[s+1], data[s]
    return data
print(bubble(data))

程序運(yùn)行后輸出結(jié)果為:

[2, 3, 4, 5, 8]

這是一種時(shí)間復(fù)雜度上限比較高的方法，它的排序時(shí)間會(huì)隨著列表長度的增加而增加。

選擇排序

選擇排序的過程和步驟如上圖所示，根據(jù)動(dòng)態(tài)圖和算法步驟， Python 實(shí)現(xiàn)選擇排序的代碼如下：

data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
def selections(nums):
    for i in range(len(nums)):
        min_index = min(nums)  # 最小值
        for j in range(len(nums) - i):
            if nums[min_index] < nums[j]:
                min_index = j
        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
    return nums
print(selections(data))

其中 min() 方法可以獲得列表中的最小值，運(yùn)行結(jié)果為：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

既然 min() 有這個(gè)特性 (備注：max() 方法可以獲得列表中最大值)，我們可以將它利用起來，騷一點(diǎn)的代碼為：

data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
res = []
for i in range(0, len(data)):
    aps = min(data)
    data.remove(aps)
    res.append(aps)
print(res)

運(yùn)行后得到的輸出結(jié)果為：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

假如將 min() 換成 max() 方法的，得到的輸出結(jié)果為：

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

這種只選擇列表最大元素或最小元素的行為，是否也能稱為選擇性排序呢？

雖然這種寫法的代碼比較短，也更容易理解。但是它的時(shí)間復(fù)雜度是如何的呢？

首先要確認(rèn) min 和 max 的時(shí)間復(fù)雜度。有人給出了 list 各項(xiàng)操作的時(shí)間復(fù)雜度：

可以看到 min 和 max 都是隨著列表長度而增長，再加上本身需要 for 循環(huán)一次，所以這種寫法的時(shí)間復(fù)雜度為

真的是這樣嗎？

代碼中有一個(gè) remove 操作，將原列表的元素刪除，但是 remove 的時(shí)間復(fù)雜度也是O(n)，這豈不是變成了 O(n*n + n)，如何解決這個(gè)問題呢。

觀察到 pop 的時(shí)間復(fù)雜度是 O(1)，那么是否可以利用 pop 來降低時(shí)間復(fù)雜度呢？list 提供了獲取元素下標(biāo)的方法，我們嘗試將代碼改為：

data = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
res = []
for i in range(0, len(data)):
    aps = max(data)
    result = data.pop(data.index(aps))
    print(result)
    res.append(aps)
print(res)

運(yùn)行后得到的輸出結(jié)果為：

9
8
7
6
5
4
3
2
1
0
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

由此可見確實(shí)能夠根據(jù)索引刪除掉 list 元素，在刪除元素這里降低了復(fù)雜度。

慢著，上述 pop 的時(shí)間復(fù)雜度是 O(1)，但是 pop(data.index(i)) 這種操作的時(shí)間復(fù)雜度呢？也是 O(1) 嗎？我們可以做個(gè)實(shí)驗(yàn)來驗(yàn)證一下：

# 崔慶才丨靜覓、韋世東丨奎因 邀請你關(guān)注微信公眾號(hào)【進(jìn)擊的Coder】
from datetime import datetime
data = [i for i in range(500000)]

start_time = datetime.now()
for i in range(len(data)):
    data.pop(data.index(i))
print(data)
print(datetime.now() - start_time)

這是 pop(data.index(i)) 的代碼，運(yùn)行結(jié)果如下：

[]
0:00:40.151812

而如果使用 pop()

from datetime import datetime
data = [i for i in range(500000)]

start_time = datetime.now()
for i in range(len(data)):
    data.pop()
print(data)
print(datetime.now() - start_time)

運(yùn)行后的結(jié)果為：

[]
0:00:00.071441

結(jié)果顯而易見，pop(i) 的時(shí)間復(fù)雜度依舊是跟元素個(gè)數(shù)有關(guān)，而不是預(yù)想中的 O(1)。由于列表元素不斷減少，所以它的時(shí)間復(fù)雜度也不是 O(n)，假設(shè)當(dāng)前列表元素?cái)?shù)量為 k，那么這個(gè)部分的時(shí)間復(fù)雜度則是 O(k)。說明簡短的 min max寫法能夠一定程度的降低時(shí)間復(fù)雜度。

驗(yàn)證一下，兩次 for 循環(huán)的選擇排序?qū)懛ê?mix max 的簡短寫法耗時(shí)情況如何：

from datetime import datetime
data = [i for i in range(30000)]


def selections(nums):
    for i in range(len(nums)):
        min_index = min(nums)  # 最小值
        for j in range(len(nums) - i):
            if nums[min_index] < nums[j]:
                min_index = j
        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
    return nums


start_time = datetime.now()
selections(data)
print(datetime.now() - start_time)

這里以 3 萬個(gè)元素為例，兩次 for 循環(huán)的運(yùn)行時(shí)間為 47 秒左右。而同樣的數(shù)量，用 min max 方式排序：

from datetime import datetime
data = [i for i in range(30000)]

start_time = datetime.now()
res = []
for i in range(0, len(data)):
    aps = max(data)
    # del data[data.index(aps)]
    data.pop(data.index(aps))
    res.append(aps)
print(datetime.now() - start_time)

所花費(fèi)的時(shí)間為 12 秒，代碼中用 del 和 pop 方法得到的結(jié)果一樣。

還……還有這種操作？

選擇排序也是一種時(shí)間復(fù)雜度上限比較高的方法，它的排序時(shí)間同樣會(huì)隨著列表長度的增加而增加。

插入排序

插入排序的過程和步驟如上圖所示，根據(jù)動(dòng)態(tài)圖和算法步驟， Python 實(shí)現(xiàn)插入排序的代碼如下：

from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)

# 崔慶才丨靜覓、韋世東丨奎因 邀請你關(guān)注微信公眾號(hào)【進(jìn)擊的Coder】
def direct_insert(nums):
    for i in range(1, len(nums)):
        temp = nums[i]  # temp變量指向尚未排好序元素（從第二個(gè)開始）
        j = i-1  # j指向前一個(gè)元素的下標(biāo)
        while j >= 0 and temp < nums[j]:
            # temp與前一個(gè)元素比較，若temp較小則前一元素后移，j自減，繼續(xù)比較
            nums[j+1] = nums[j]
            j = j-1
            nums[j+1] = temp  # temp所指向元素的最終位置
    return nums


start_time = datetime.now()
res = direct_insert(data)
print(datetime.now() - start_time)
print(len(res), res[:10])

生成列表后在列索引為 60 的地方插入一個(gè)值為 5 的元素，現(xiàn)在數(shù)據(jù)量為 3 萬零 1。代碼運(yùn)行得到的輸出結(jié)果為：

0:00:00.007398
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]

可以看到 3 萬零 1 個(gè)元素的列表排序耗時(shí)很短，而且通過切片可以看到順序已經(jīng)經(jīng)過排列。

然后測試一下選擇，代碼如下：

from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)


def selections(nums):
    for i in range(len(nums)):
        min_index = min(nums)  # 最小值
        for j in range(len(nums) - i):
            if nums[min_index] < nums[j]:
                min_index = j
        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1], nums[min_index]
    return nums


start_time = datetime.now()
res = selections(data)
print(datetime.now() - start_time)
print(len(res), res[:10])

代碼運(yùn)行后得到的輸出結(jié)果為：

0:00:47.895237
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]

可以看到 3 萬零 1 個(gè)元素的列表排序耗并不短，耗費(fèi)了 47 秒鐘，通過切片可以看到順序已經(jīng)經(jīng)過排列。

接著試一下 max min 型選擇排序的寫法，得到的結(jié)果為：

0:00:14.150992
30001 [29999, 29998, 29997, 29996, 29995, 29994, 29993, 29992, 29991, 29990]

這簡直了，為什么這種操作就能夠節(jié)省這么多時(shí)間呢？

最后測試一下冒泡：

# 崔慶才丨靜覓、韋世東丨奎因 邀請你關(guān)注微信公眾號(hào)【進(jìn)擊的Coder】
from datetime import datetime
data = [i for i in range(30000)]
data.insert(60, 5)


def bubble(data):
    for i in range(len(data)-1):    # 排序次數(shù)
        for s in range(len(data)-i-1):  # s為列表下標(biāo)
            if data[s] > data[s+1]:
                data[s], data[s+1] = data[s+1], data[s]
    return data


start_time = datetime.now()
res = bubble(data)
print(datetime.now() - start_time)
print(len(res), res[:10])

代碼運(yùn)行后得到的輸出結(jié)果為：

0:00:41.392303
30001 [0, 1, 2, 3, 4, 5, 5, 6, 7, 8]

可以看到 3 萬零 1 個(gè)元素的列表排序耗并不短，耗費(fèi)了 41 秒鐘，通過切片可以看到順序已經(jīng)經(jīng)過排列。

得到的結(jié)果為：

• 冒泡排序  - 41

• 選擇排序（兩層 for）  - 47

• 選擇排序（max mix）  - 14

• 插入排序  - 0.007398

問題：實(shí)在是令人匪夷所思，插入排序的速度居然比其他兩種排序方式耗時(shí)少那么多。這是為什么呢？

事實(shí)上插入排序只用了 1 層 for 循環(huán)，并非像冒泡和選擇那樣使用 2 層 for 循環(huán)，是不是由此可以刷新上圖中對于時(shí)間復(fù)雜度的介紹呢？

問題：而兩種不同的選擇排序法的結(jié)果差異這么大，這又是為什么？？？

請?jiān)谠u(píng)論區(qū)發(fā)表你的看法