Python 一網打盡＜排序演算法＞之從希爾排序演算法的分治哲學開始

1. 前言

本文將介紹希爾排序、歸并排序、基數排序（桶排序），

在所有的排序演算法中，冒泡、插入、選擇屬于相類似的排序演算法，這類演算法的共同點：通過不停地比較，再使用交換邏輯重新確定資料的位置，

希爾、歸并、快速排序演算法也可歸為同一類，它們的共同點都是建立在分治思想之上，把大問題分拆成小問題，解決所有小問題后，再合并每一個小問題的結果，最終得到對原始問題的解答，

通俗而言：化整為零，各個擊破，

分治演算法很有哲學蘊味：老祖宗所言 合久必分，分久必合，分開地目的是為了更好的合并，

分治演算法的求解流程：

• 分解問題：將一個需要解決的、看起很復雜 原始問題 分拆成很多獨立的子問題，子問題與原始問題有相似性，

  如：一個數列的區域（小問題）有序，必然會讓數列最終（原始問題）有序，

• 求解子問題：子問題除了與原始問題具有相似性，也具有獨立性，即所有子問題都可以獨立求解，

• 合并子問題：合并每一個子問題的求解結果最終可以得到原始問題的解，

下面通過深入了解希爾排序演算法，看看分治演算法是如何以哲學之美的方式作業的，

2. 希爾排序

講解希爾之前，先要回顧一下插入排序，插入排序的平均時間復雜度，理論上而言和冒泡排序是一樣的 O（n²），但如果數列是前部分有序，則每一輪只需比較一次，對于 n 個數字的原始數列而言，時間復雜度可以是達到 O(n)，

插入排序的時間復雜度為什么會出現如此有意思的變化？

• 插入排序演算法的排序思想是盡可能減少數字之間的交換次數，
• 通常情形下，交換處理的時間大約是移動的 3 倍，這便是插入排序的性能有可能要優于冒泡排序的原因，

希爾排序演算法本質就是插入排序，或說是對插入排序的改良，

其演算法理念：讓原始數列不斷趨近于排序，從而降低插入排序的時間復雜度，

希爾排序的實作流程：

• 把原始數列從邏輯上切割成諸多個子數列，
• 對每一個子數列使用插入排序演算法排序，
• 當所有子數列完成后，再對原數列進行最后一次插入演算法排序，

希爾排序演算法的理念：當數列區域有序時，全域必然是趨向于有序”，

希爾排序的關鍵在于如何切分子數列，切分方式可以有 2 種：

任何時候使用分治理念解決問題時，分拆子問題都是關鍵的也是核心的，

2.1 前后切分

如有原始數列=[3，9，8，1，6，5，7] 采用前后分成 2 個子數列，

前后分算得上是簡單粗暴的切分方案，沒有太多技術含量，這種一根筋的切分方式，對于原始問題的最終性能優化可能起不了太多影響，

如上圖所示，對子數列排序后，如果要實作原始數列中的所有數字從小到大排列有序，則后部分的數字差不多全部要移到時前部分數字的中間，其移動量是非常大的，

后面的 4 個數字中，1 需要移動 3 次，5、6、7 需要移動 2 次， 肉眼可見的次數是 9 次，

這種分法很難實作數字區域有序的正態分布，因為數字的位置變化不大，

如下圖是原始數列=[3，9，8，1，6，5，7] 的原始位置示意圖：

使用前后切分后的數字位置變化如下圖所示，和上圖相比較，數字的位置變化非常有限，而且是限定在一個很窄的范圍內，也就是說子問題的求解結果對最終問題的結果的影響很微小，

2.2 增量切分

增量切分采用間隔切分方案，可能讓數字區域有序以正態分布，

增量切分，需要先設定一個增量值，如對原始數列=[3，9，8，1，6，5，7] 設定切分增量為 3 時，整個數列會被切分成 3 個邏輯子數列，增量數也決定最后能切分多少個子數列，

對切分后的 3 個子數列排序后可得到下圖：

在此基礎之上，再進行插入排序的的次數要少很多，

使用增量切分后再排序，原始數列中的數字的位置變化范圍較大，

如數字 9 原始位置是 1，經過增量切分再排序后位置可以到 4，已經很接近 9 的最終位置 6 了，

下圖是增量切分后數字位置的變化圖，可以看出來，幾乎所有的數字都產生了位置變化 ，且位置變化的跨度較大，有整體趨于有序的勢頭，

實作希爾排序演算法時，最佳的方案是先初始化一個增量值，切分排序后再減少增量值，如此反復直到增量值等于 1 （也就是對原數列整體做插入排序），

增量值大，數字位置變化的跨度就大，增量值小，數字位置的變化會收緊，

編碼代碼希爾排序：

# 希爾排序
def shell_sort(nums):
    # 增量
    increment = len(nums) // 2
    # 新數列
    while increment > 0:
        # 增量值是多少，則切分的子數列就有多少
        for start in range(increment):
            insert_sort(nums, start, increment)
        # 修改增量值，直到增量值為 1    
        increment = increment // 2
        
# 插入排序
def insert_sort(nums, start, increment):
    for back_idx in range(start + increment, len(nums), increment):
        for front_idx in range(back_idx, 0, -increment):
            if nums[front_idx] < nums[front_idx - increment]:
                nums[front_idx], nums[front_idx - increment] = nums[front_idx - increment], nums[front_idx]
            else:
                break

nums = [3, 9, 8, 1, 6, 5, 7]
shell_sort(nums)
print(nums)

這里會有一個讓人疑惑的觀點：難道一次插入排序的時間復雜度會高于多次插入排序時間復雜度？

通過切分方案，經過子數列的微排序（因子數列數字不多，其移動交換量也不會很大），最后一次插入排序的移動次數可以達到最小，只要增量選擇合適，時間復雜度可以控制 在 O(n) 到 O（<sup>2</sup>） 之間，完全是有可能優于單純的使用一次插入排序，

3. 歸并排序

歸并排序演算法也是基于分治思想，和希爾排序一樣，需要對原始數列進行切分，但是切分的方案不一樣，

相比較希爾排序，歸并排序的分解子問題，求解子問題，合并子問題的程序分界線非常清晰，可以說，歸并排序更能完美詮釋什么是分治思想，

3.1 分解子問題

歸并排序演算法的分解程序采用二分方案，

• 把原始數列一分為二，

• 然后在已經切分后的子數列上又進行二分，

• 如此反復，直到子數列不能再分為止，

  如下圖所示：

如下代碼，使用遞回演算法對原數列進行切分，通過輸出結果觀察切分程序：

# 切分原數列
def split_nums(nums):
    print(nums)
    if len(nums) > 1:
        # 切分線，中間位置
        sp_line = len(nums) // 2
        split_nums(nums[0:sp_line])
        split_nums(nums[sp_line:])

nums = [3, 9, 8, 1, 6, 5, 7]
split_nums(nums)

輸出結果：和上面演示圖的結論一樣，

[3, 9, 8, 1, 6, 5, 7]
[3, 9, 8]
[3]
[9, 8]
[9]
[8]
[1, 6, 5, 7]
[1, 6]
[1]
[6]
[5, 7]
[5]
[7]

3.2 求解子問題

切分后，對每相鄰 2 個子數列進行合并，當對相鄰 2 個數列進行合并時，不是簡單合并，需要保證合并后的數字是排序的，如下圖所示：

3.3 合并排序

如何實作 2 個數字合并后數字有序？

使用子數列中首數字比較演算法進行合并排序，如下圖演示了如何合并 nums01=[1,3,8,9]、nums02=[5,6,7] 2 個子數列，

子數列必須是有序的！！

• 數字 1 和 數字 5 比較，5 大于 1 ，數字 1 先位于合并數列中，

• 數字 3 與數字 5 比較，數字 3 先進入合并數列中，

• 數字 8 和數字 5 比較，數字 5 進入合并數列中，

從頭至尾，進行首數字大小比較，最后，可以保證合并后的數列是有序的，

撰寫一個合并排序代碼：

如果僅僅是合并 2 個有序數列，本文提供 2 個方案：

• 不增加額外的存盤空間：把最終合并排序好的數字全部存盤到其中的一個數列中，

def merge_sort(nums01, nums02):
    # 為 2 個數列創建 2 個指標
    idx_01 = 0
    idx_02 = 0
    while idx_01 < len(nums01) and idx_02 < len(nums02):
        if nums01[idx_01] > nums02[idx_02]:
            # 這里不額外增加存盤空間，如果數列 2 中的值大于數字 1 的插入到數列 1 中
            nums01.insert(idx_01, nums02[idx_02])
            idx_02 += 1
        # 數列 1 的指標向右移動    
        idx_01 += 1
    # 檢查 nums02 中的數字是否已經全部合并到 nums01 中
    while idx_02 < len(nums02):
        nums01.append(nums02[idx_02])
        idx_02 += 1

nums01 = [1, 2, 8, 9]
nums02 = [5, 6, 7, 12, 15]
merge_sort(nums01, nums02)
# 合并后的數字都存盤到了第一個數列中
print(nums01)
'''
輸出結果：
[1,2,5,6,7,8,9,12,15]
'''

• 增加一個空數列，用來保存最終合并的數字，

# 使用附加數列
nums=[]
def merge_sort(nums01, nums02):
    # 為 2 個數列創建 2 個指標
    idx_01 = 0
    idx_02 = 0
    k=0
    while idx_01 < len(nums01) and idx_02 < len(nums02):
        if nums01[idx_01] > nums02[idx_02]:
            nums.append(nums02[idx_02])
            idx_02 += 1
        else:
            nums.append(nums01[idx_01])
            idx_01 += 1
        k+=1
    # 檢查是否全部合并
    while idx_02 < len(nums02):
        nums.append(nums02[idx_02])
        idx_02 += 1
    while idx_01 < len(nums01):
        nums.append(nums01[idx_01])
        idx_01 += 1

nums01 = [1, 2, 8, 9]
nums02 = [5, 6, 7, 12, 15]
merge_sort(nums01, nums02)
print(nums)

前面是分步講解切分和合并邏輯，現在把切分和合并邏輯合二為一，就完成了歸并演算法的實作：

def merge_sort(nums):
    if len(nums) > 1:
        # 切分線，中間位置
        sp_line = len(nums) // 2
        nums01 = nums[:sp_line]
        nums02 = nums[sp_line:]
        merge_sort(nums01)
        merge_sort(nums02)

        # 為 2 個數列創建 2 個指標
        idx_01 = 0
        idx_02 = 0
        k = 0
        while idx_01 < len(nums01) and idx_02 < len(nums02):
            if nums01[idx_01] > nums02[idx_02]:
                # 合并后的數字要保存到原數列中
                nums[k] = nums02[idx_02]
                idx_02 += 1
            else:
                nums[k] = nums01[idx_01]
                idx_01 += 1
            k += 1
        # 檢查是否全部合并
        while idx_02 < len(nums02):
            nums[k] = nums02[idx_02]
            idx_02 += 1
            k += 1
        while idx_01 < len(nums01):
            nums[k] = nums01[idx_01]
            idx_01 += 1
            k += 1

nums = [3, 9, 8, 1, 6, 5, 7]
merge_sort(nums)
print(nums)

個人覺得，歸并演算法對于理解分治思想有大的幫助，

從歸并演算法上可以完整的體現分治理念的哲學之美，

4. 基數排序

基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或 bin sort，

基數排序沒有使用分治理念，放在本文一起講解，是因為基數排序有一個對數字自身切分邏輯，

基數排序的最基本思想：

如對原始數列 nums = [3, 9, 8, 1, 6, 5, 7] 中的數字使用基數排序，

• 先提供一個長度為 10 的新空數列（本文也稱為排序數列），

  為什么新空數列的長度要設定為 10？等排序完畢，相信大家就能找到答案，

，把原數列中的數字轉存到新空數列中，轉存方案：

nums 中的數字 3 存盤在新數列索引號為 3 的位置，

nums 中的數字 9 存盤在新數列索引號為 9 的位置，

nums 中的數字 8 存盤在新數列索引號為 8 的位置，

……

從上圖可知，原數列中的數字所轉存到排序數列中的位置，是數字所代表的索引號所指的位置，顯然，經過轉存后，新數列就是一個排好序的數列，

新空數列的長度定義為多大由原始數列中數字的最大值來決定，

編碼實作：

# 原數列
nums = [3, 9, 8, 1, 6, 5, 7]
# 找到數列中的最大值
sort_nums=[0]*(max(nums)+1)
for i in nums:
    sort_nums[i]=i

print([i for i in sort_nums if i!=0])
'''
輸出結果：
[1,3,5,6,7,8,9]
'''

使用上述方案創建新空資料，如果數字之間的間隔較大時，新數列的空間浪費就非常大，

如對 nums=[1,98,51,2,32,4,99,13,45] 使用上述方案排序，新空數列的長度要達到 99 ，真正需要保存的數字只有 7 個，如此空間浪費幾乎是令人恐怖的，

所以，有必要使用改良方案，如果在需要排序的數字中出現了 2 位以上的數字，則使用如下法則：

• 先根據每一個數字個位上的數字進行存盤，個位數是 1 存盤在位置為 1 的位置，是 9 就存盤在位置是 9 的位置，如下圖：

可看到有可能在同一個位置保存多個數字，這也是基數排序也稱為桶排序的原因，

一個位置就是一個桶，可以存放多個具有相同性質的數字，如上圖：個位上數字相同的數字就在一個桶中，

• 把存放在排序數列中的數字按順序重新拿出來，這時的數列順序變成 nums=[1，51，2，32，13，4，45，8，99]
• 把重組后數列中的數字按十位上的數字重新存入排序數列，

可以看到，經過 2 輪轉存后，原數列就已經排好序，

這個道理是很好理解的：

現實生活中，我們在比較 2 個數字 大小時，可以先從個位上的數字相比較，然后再對十位上的數字比較，

基數排序，很有生活的味道！！

編碼實作基數排序：

nums = [1, 98, 51, 2, 32, 4, 99, 13, 45]
# 數列中的最大值
m = max(nums)
# 確定最大位數，用來確定需要轉存多少次
l = len(str(m))

for i in range(l + 1):
    # 排序數列，也是桶
    sort_nums = [[] for _ in range(10)]
    for n in nums:
        # 分解數字個位上的數字
        g_s = (n // 10 ** i) % 10
        # 根據個位上的數字找到轉存位置
        sub_nums = sort_nums[g_s]
        sub_nums.append(n)
    # 合并資料
    nums = []
    for l in sort_nums:
        nums.extend(l)
print(nums)
'''
輸出結果：
[1, 2, 4, 13, 32, 45, 51, 98, 99]
'''

上述轉存程序是由低位到高位，也稱為 LSD ，也可以先高位后低位方案轉存MSD，

5. 總結

分治很有哲學味道，當你遇到困難，應該試著找到問題的薄弱點，然后一點點地突破，

當遇到困難時，老師們總會這么勸解我們，

分治其實和專案開發中的組件設計思想也具有同工異曲之處，

標籤：Python

上一篇：python運算子

下一篇：python回圈陳述句