“

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

”

閱讀本文可以幫助你解開以下疑惑：算法是什么？算法難不難？怎么才能夠在短時間內熟悉業內的經典算法呢？這些算法用 Python 實現會是什么樣的？它們的耗時會跟時間復雜度相關嗎？

神馬是算法？

算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出并停止于一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在內的一些算法，包含了一些隨機輸入。

算法的幾大特征

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

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

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

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

• 輸出項 (Output) -- 一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的；

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

算法兩大要素

• 一，數據對象的運算和操作：計算機可以執行的基本操作是以指令的形式描述的。一個計算機系統能執行的所有指令的集合，成為該計算機系統的指令系統。一個計算機的基本運算和操作有如下四類：

• 1 算術運算：加減乘除等運算

• 2 邏輯運算：或、且、非等運算

• 3 關系運算：大于、小于、等于、不等于等運算

• 4 數據傳輸：輸入、輸出、賦值等運算 [1]

• 二，算法的控制結構：一個算法的功能結構不僅取決于所選用的操作，而且還與各操作之間的執行順序有關。

算法的好壞評定

你說這個算法好、他卻說這個算法不好，兩人爭論不休。那么好與不好應該怎么評定呢？

同一問題可用不同算法解決，而一個算法的質量優劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進算法。一個算法的評價主要從時間復雜度和空間復雜度來考慮。

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

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

• 正確性 - 算法的正確性是評價一個算法優劣的最重要的標準。

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

• 健壯性 - 健壯性是指一個算法對不合理數據輸入的反應能力和處理能力，也稱為容錯性。

以上的理論知識可以讓我們對算法有個大致的理解和認知，接下來我們將使用 Python 實現幾個經典的 排序算法，并在文末對比 Java 的實現。

算法的內外之分

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

• 內部排序指的是在內存中進行排序；

• 外部排序指的是由于數據量較大，無法讀入內存而需要在排序過程中訪問外部存儲的情況；

比較經典的排序算法如下圖所示：

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

它們各自的時間復雜度如下圖所示：

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

在開始之前，首先要感謝公眾號《五分鐘學算法》的大佬 “程序員小吳” 授權動態圖片和排序思路。

冒泡排序

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

根據動態圖和算法步驟， Python 實現冒泡排序的代碼如下：

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

程序運行后輸出結果為:

[2, 3, 4, 5, 8]

這是一種時間復雜度上限比較高的方法，它的排序時間會隨著列表長度的增加而增加。

選擇排序

選擇排序的過程和步驟如上圖所示，根據動態圖和算法步驟， Python 實現選擇排序的代碼如下：

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() 方法可以獲得列表中的最小值，運行結果為：

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

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

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)

運行后得到的輸出結果為：

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

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

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

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

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

首先要確認 min 和 max 的時間復雜度。有人給出了 list 各項操作的時間復雜度：

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

真的是這樣嗎？

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

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

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)

運行后得到的輸出結果為：

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

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

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

# 崔慶才丨靜覓、韋世東丨奎因 邀請你關注微信公眾號【進擊的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)) 的代碼，運行結果如下：

[]
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)

運行后的結果為：

[]
0:00:00.071441

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

驗證一下，兩次 for 循環的選擇排序寫法和 mix max 的簡短寫法耗時情況如何：

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 萬個元素為例，兩次 for 循環的運行時間為 47 秒左右。而同樣的數量，用 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)

所花費的時間為 12 秒，代碼中用 del 和 pop 方法得到的結果一樣。

還……還有這種操作？

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

插入排序

插入排序的過程和步驟如上圖所示，根據動態圖和算法步驟， Python 實現插入排序的代碼如下：

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

# 崔慶才丨靜覓、韋世東丨奎因 邀請你關注微信公眾號【進擊的Coder】
def direct_insert(nums):
    for i in range(1, len(nums)):
        temp = nums[i]  # temp變量指向尚未排好序元素（從第二個開始）
        j = i-1  # j指向前一個元素的下標
        while j >= 0 and temp < nums[j]:
            # temp與前一個元素比較，若temp較小則前一元素后移，j自減，繼續比較
            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 的地方插入一個值為 5 的元素，現在數據量為 3 萬零 1。代碼運行得到的輸出結果為：

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

可以看到 3 萬零 1 個元素的列表排序耗時很短，而且通過切片可以看到順序已經經過排列。

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

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])

代碼運行后得到的輸出結果為：

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

可以看到 3 萬零 1 個元素的列表排序耗并不短，耗費了 47 秒鐘，通過切片可以看到順序已經經過排列。

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

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

這簡直了，為什么這種操作就能夠節省這么多時間呢？

最后測試一下冒泡：

# 崔慶才丨靜覓、韋世東丨奎因 邀請你關注微信公眾號【進擊的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):    # 排序次數
        for s in range(len(data)-i-1):  # s為列表下標
            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])

代碼運行后得到的輸出結果為：

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

可以看到 3 萬零 1 個元素的列表排序耗并不短，耗費了 41 秒鐘，通過切片可以看到順序已經經過排列。

得到的結果為：

• 冒泡排序  - 41

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

• 選擇排序（max mix）  - 14

• 插入排序  - 0.007398

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

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

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

請在評論區發表你的看法