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. 歸并排序

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

相比較希爾排序，歸并排序的分解子問題，求解子問題，合并子問題的過程分界線非常清晰?？梢哉f，歸并排序更能完美詮釋什么是分治思想。

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. 總結

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

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

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