快捷導(dǎo)航

Python實(shí)現(xiàn)希爾排序,歸并排序和桶排序的示例代碼

更新時(shí)間：2022年04月24日 17:01:58 作者：一枚大果殼

希爾、歸并、快速排序算法可歸為同一類，它們的共同點(diǎn)都是建立在分治思想之上。把大問題分拆成小問題，解決所有小問題后，再合并每一個(gè)小問題的結(jié)果，最終得到對原始問題的解答。本文將介紹這三種算法的實(shí)現(xiàn)代碼，需要的可以參考一下

1. 前言

本文將介紹希爾排序、歸并排序、基數(shù)排序（桶排序）。

在所有的排序算法中，冒泡、插入、選擇屬于相類似的排序算法，這類算法的共同點(diǎn)：通過不停地比較，再使用交換邏輯重新確定數(shù)據(jù)的位置。

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

通俗而言：化整為零，各個(gè)擊破。

分治算法很有哲學(xué)蘊(yùn)味：老祖宗所言合久必分，分久必合，分開地目的是為了更好的合并。

分治算法的求解流程：

分解問題：將一個(gè)需要解決的、看起很復(fù)雜原始問題分拆成很多獨(dú)立的子問題，子問題與原始問題有相似性。

如：一個(gè)數(shù)列的局部（小問題）有序，必然會讓數(shù)列最終（原始問題）有序。

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

合并子問題：合并每一個(gè)子問題的求解結(jié)果最終可以得到原始問題的解。

下面通過深入了解希爾排序算法，看看分治算法是如何以哲學(xué)之美的方式工作的。

2. 希爾排序

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

插入排序的時(shí)間復(fù)雜度為什么會出現(xiàn)如此有意思的變化？

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

希爾排序算法本質(zhì)就是插入排序，或說是對插入排序的改良。

其算法理念：讓原始數(shù)列不斷趨近于排序，從而降低插入排序的時(shí)間復(fù)雜度。

希爾排序的實(shí)現(xiàn)流程：

把原始數(shù)列從邏輯上切割成諸多個(gè)子數(shù)列。
對每一個(gè)子數(shù)列使用插入排序算法排序。
當(dāng)所有子數(shù)列完成后，再對原數(shù)列進(jìn)行最后一次插入算法排序。

希爾排序算法的理念：當(dāng)數(shù)列局部有序時(shí)，全局必然是趨向于有序”。

希爾排序的關(guān)鍵在于如何切分子數(shù)列，切分方式可以有 2 種：

任何時(shí)候使用分治理念解決問題時(shí)，分拆子問題都是關(guān)鍵的也是核心的。

2.1 前后切分

如有原始數(shù)列=[3，9，8，1，6，5，7] 采用前后分成 2 個(gè)子數(shù)列。

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

如上圖所示，對子數(shù)列排序后，如果要實(shí)現(xiàn)原始數(shù)列中的所有數(shù)字從小到大排列有序，則后部分的數(shù)字差不多全部要移到時(shí)前部分?jǐn)?shù)字的中間，其移動量是非常大的。

后面的 4 個(gè)數(shù)字中，1 需要移動 3 次，5、6、7 需要移動 2 次，肉眼可見的次數(shù)是 9 次。

這種分法很難實(shí)現(xiàn)數(shù)字局部有序的正態(tài)分布，因?yàn)?strong>數(shù)字的位置變化不大。

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

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

2.2 增量切分

增量切分采用間隔切分方案，可能讓數(shù)字局部有序以正態(tài)分布。

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

對切分后的 3 個(gè)子數(shù)列排序后可得到下圖：

在此基礎(chǔ)之上，再進(jìn)行插入排序的的次數(shù)要少很多。

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

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

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

實(shí)現(xiàn)希爾排序算法時(shí)，最佳的方案是先初始化一個(gè)增量值，切分排序后再減少增量值，如此反復(fù)直到增量值等于 1 （也就是對原數(shù)列整體做插入排序）。

增量值大，數(shù)字位置變化的跨度就大，增量值小，數(shù)字位置的變化會收緊。

編碼代碼希爾排序：

# 希爾排序
def shell_sort(nums):
    # 增量
    increment = len(nums) // 2
    # 新數(shù)列
    while increment > 0:
        # 增量值是多少，則切分的子數(shù)列就有多少
        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)

這里會有一個(gè)讓人疑惑的觀點(diǎn)：難道一次插入排序的時(shí)間復(fù)雜度會高于多次插入排序時(shí)間復(fù)雜度？

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

3. 歸并排序

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

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

3.1 分解子問題

歸并排序算法的分解過程采用二分方案。

把原始數(shù)列一分為二。

然后在已經(jīng)切分后的子數(shù)列上又進(jìn)行二分。

如此反復(fù)，直到子數(shù)列不能再分為止。

如下圖所示：

如下代碼，使用遞歸算法對原數(shù)列進(jìn)行切分，通過輸出結(jié)果觀察切分過程：

# 切分原數(shù)列
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)

輸出結(jié)果：和上面演示圖的結(jié)論一樣。

[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 個(gè)子數(shù)列進(jìn)行合并。當(dāng)對相鄰 2 個(gè)數(shù)列進(jìn)行合并時(shí)，不是簡單合并，需要保證合并后的數(shù)字是排序的。如下圖所示：

3.3 合并排序

如何實(shí)現(xiàn) 2 個(gè)數(shù)字合并后數(shù)字有序？

使用子數(shù)列中首數(shù)字比較算法進(jìn)行合并排序。如下圖演示了如何合并 nums01=[1,3,8,9]、nums02=[5,6,7] 2 個(gè)子數(shù)列。

子數(shù)列必須是有序的?。?/p>

數(shù)字 1 和數(shù)字 5 比較，5 大于 1 ，數(shù)字 1 先位于合并數(shù)列中。

數(shù)字 3 與數(shù)字 5 比較，數(shù)字 3 先進(jìn)入合并數(shù)列中。

數(shù)字 8 和數(shù)字 5 比較，數(shù)字 5 進(jìn)入合并數(shù)列中。

從頭至尾，進(jìn)行首數(shù)字大小比較，最后，可以保證合并后的數(shù)列是有序的。

編寫一個(gè)合并排序代碼：

如果僅僅是合并 2 個(gè)有序數(shù)列，本文提供 2 個(gè)方案：

不增加額外的存儲空間：把最終合并排序好的數(shù)字全部存儲到其中的一個(gè)數(shù)列中。

def merge_sort(nums01, nums02):
    # 為 2 個(gè)數(shù)列創(chuàng)建 2 個(gè)指針
    idx_01 = 0
    idx_02 = 0
    while idx_01 < len(nums01) and idx_02 < len(nums02):
        if nums01[idx_01] > nums02[idx_02]:
            # 這里不額外增加存儲空間，如果數(shù)列 2 中的值大于數(shù)字 1 的插入到數(shù)列 1 中
            nums01.insert(idx_01, nums02[idx_02])
            idx_02 += 1
        # 數(shù)列 1 的指針向右移動    
        idx_01 += 1
    # 檢查 nums02 中的數(shù)字是否已經(jīng)全部合并到 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)
# 合并后的數(shù)字都存儲到了第一個(gè)數(shù)列中
print(nums01)
'''
輸出結(jié)果：
[1,2,5,6,7,8,9,12,15]
'''

增加一個(gè)空數(shù)列，用來保存最終合并的數(shù)字。

# 使用附加數(shù)列
nums=[]
def merge_sort(nums01, nums02):
    # 為 2 個(gè)數(shù)列創(chuàng)建 2 個(gè)指針
    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)

前面是分步講解切分和合并邏輯，現(xiàn)在把切分和合并邏輯合二為一，就完成了歸并算法的實(shí)現(xiàn)：

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 個(gè)數(shù)列創(chuàng)建 2 個(gè)指針
        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]:
                # 合并后的數(shù)字要保存到原數(shù)列中
                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)

個(gè)人覺得，歸并算法對于理解分治思想有大的幫助。

從歸并算法上可以完整的體現(xiàn)分治理念的哲學(xué)之美。

4. 基數(shù)排序

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

基數(shù)排序沒有使用分治理念，放在本文一起講解，是因?yàn)榛鶖?shù)排序有一個(gè)對數(shù)字自身切分邏輯。

基數(shù)排序的最基本思想：

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

先提供一個(gè)長度為 10 的新空數(shù)列（本文也稱為排序數(shù)列）。

為什么新空數(shù)列的長度要設(shè)置為 10？等排序完畢，相信大家就能找到答案。

把原數(shù)列中的數(shù)字轉(zhuǎn)存到新空數(shù)列中，轉(zhuǎn)存方案：

nums 中的數(shù)字 3 存儲在新數(shù)列索引號為 3 的位置。

nums 中的數(shù)字 9 存儲在新數(shù)列索引號為 9 的位置。

nums 中的數(shù)字 8 存儲在新數(shù)列索引號為 8 的位置。

……

從上圖可知，原數(shù)列中的數(shù)字所轉(zhuǎn)存到排序數(shù)列中的位置，是數(shù)字所代表的索引號所指的位置。顯然，經(jīng)過轉(zhuǎn)存后，新數(shù)列就是一個(gè)排好序的數(shù)列。

新空數(shù)列的長度定義為多大由原始數(shù)列中數(shù)字的最大值來決定。

編碼實(shí)現(xiàn)：

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

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

使用上述方案創(chuàng)建新空數(shù)據(jù)，如果數(shù)字之間的間隔較大時(shí)，新數(shù)列的空間浪費(fèi)就非常大。

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

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

先根據(jù)每一個(gè)數(shù)字個(gè)位上的數(shù)字進(jìn)行存儲。個(gè)位數(shù)是 1 存儲在位置為 1 的位置，是 9 就存儲在位置是 9 的位置。如下圖：

可看到有可能在同一個(gè)位置保存多個(gè)數(shù)字。這也是基數(shù)排序也稱為桶排序的原因。

一個(gè)位置就是一個(gè)桶，可以存放多個(gè)具有相同性質(zhì)的數(shù)字。如上圖：個(gè)位上數(shù)字相同的數(shù)字就在一個(gè)桶中。

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

可以看到，經(jīng)過 2 輪轉(zhuǎn)存后，原數(shù)列就已經(jīng)排好序。

這個(gè)道理是很好理解的：

現(xiàn)實(shí)生活中，我們在比較 2 個(gè)數(shù)字大小時(shí)，可以先從個(gè)位上的數(shù)字相比較，然后再對十位上的數(shù)字比較。

基數(shù)排序，很有生活的味道??！

編碼實(shí)現(xiàn)基數(shù)排序：

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

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

上述轉(zhuǎn)存過程是由低位到高位，也稱為 LSD ，也可以先高位后低位方案轉(zhuǎn)存MSD。