希爾排序

今天我們來介紹一個比經(jīng)典的排序算法：希爾排序。該算法時以它的發(fā)明者 Donald Shell 名字命名的，改進自插入排序算法，實現(xiàn)簡單，在中等規(guī)模的數(shù)據(jù)上性能表現(xiàn)不錯。我們同樣從算法的思路、Python 實現(xiàn)以及復雜度分析三個方面學習希爾排序算法。

1. 希爾排序算法思路

希爾排序又叫縮小增量排序，它是基于插入排序的改進算法，相比插入排序更加高效，但是屬于不穩(wěn)定算法，而插入排序則是一種穩(wěn)定算法。希爾排序的基本思想是將待排序元素進行增量分組，然后在分組組內(nèi)進行插入排序，隨著增量的減少，每個分組組內(nèi)的元素越來越多，直至增量減至1時，所有元素都分到同一個組內(nèi)，執(zhí)行插入排序后完成整個排序操作。希爾排序通過這種策略使得整個數(shù)組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在后。然后縮小增量，到增量為1時，其實多數(shù)情況下只需微調即可，不會涉及過多的數(shù)據(jù)移動。

2. 舉例說明希爾排序算法過程

下面以 8 個數(shù)的列表為例，描述希爾排序算法的排序過程。

3. 希爾排序復雜度分析

希爾排序的時間復雜度比較難計算，這里直接給出相關結果：

• 時間復雜度：最壞情況下，每兩個數(shù)都要比較并交換一次，因此最壞情況下的時間復雜度為$O(n^2)$最好情況下，數(shù)組是有序的，不需要交換，只需要比較，因此最好情況下的時間復雜度為 $O(n)$；它的平均復雜度可以達到 $O(n^{1.3})$；

• 空間復雜度：由于采用數(shù)據(jù)交換的方式，并沒有用到額外的空間，所以空間復雜度為 $O(1)$。

4. 希爾排序算法的 Python 實現(xiàn)

希爾排序的一個經(jīng)典實現(xiàn)如下所示，接下來我們會畫圖描述下該代碼的實現(xiàn)過程。

def shell_sort(nums):
    """
    希爾排序
    """
    n = len(nums)
    d = n // 2
  
    while d > 0: 
        for i in range(d, n): 
            temp = nums[i] 
            j = i 
            # 插入排序過程，可參考下圖所示
            while j >= d and nums[j - d] > temp: 
                nums[j] = nums[j - d] 
                j -= d 
            nums[j] = temp
        # 每次排序數(shù)組間距減半
        d = d // 2

我們畫圖來對上述算法進行說明，它并沒有完整依照前面的 shell 過程進行實現(xiàn)，不過執(zhí)行過程和 shell 排序的思路是一致的。

希爾排序的代碼已經(jīng)在上圖中解釋的非常清楚了，for 循環(huán)中每次會將該位置往前間隔 d 的列表保證有序，后面每次會在間隔 d 的列表中將 nums[i] 插入到對應的位置，并保證本次從該位置往前間隔為 d 的列表有序。每次 for 循環(huán)執(zhí)行完成，間隔為 d 的列表就是有序的，即完成了希爾排序的核心過程。 接下來便是每次縮小增量 d 值，直到最后增量為0，排序結束。

5. 實例測試希爾排序代碼

我們來測試希爾排序算法的性能，使用10000個隨機數(shù)進行測試：

import random
import datetime
from sort_algorithms import shell_sort, insert_sort2

if __name__ == '__main__':
    nums = [random.randint(10, 10000) for i in range(10000)] 
    start = datetime.datetime.now()
    shell_sort(nums)
    # insert_sort2(nums)
    end = datetime.datetime.now()
    print('Running time: %s Seconds' % (end-start))

PS C:\Users\spyinx\Desktop\學習教程\慕課網(wǎng)教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網(wǎng)教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.071001 Seconds

然后來看看我們用前面改進的插入排序算法 (使用前面完成的 insert_sort2() 方法) 進行測試并和希爾排序的結果對比?？梢钥吹较柵判虻男阅艽蟾攀遣迦肱判蛩惴ǖ?3 倍，所以希爾排序相比插入排序算法性能提升還是非常明顯的。

PS C:\Users\spyinx\Desktop\學習教程\慕課網(wǎng)教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網(wǎng)教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.216178 Seconds

6. 小結

本節(jié)我們學習了排序中的一個經(jīng)典排序算法：希爾排序，相比前面的冒泡、插入和選擇排序算法在效率是有了較大提升。接下來我們要學習最后一個最常考也是面試中最常見的排序算法：快速排序算法。