python排序算法之希爾排序怎么實現

Python排序算法之希爾排序怎么實現

希爾排序（Shell Sort）是一種基于插入排序的排序算法，由Donald Shell于1959年提出。它通過將待排序的數組分割成若干個子序列，分別進行插入排序，隨著子序列逐漸變短，最終整個數組變得基本有序，最后再進行一次插入排序。希爾排序的核心思想是通過逐步減少增量（gap）來使得數組逐漸趨于有序。

希爾排序的基本思想

希爾排序的基本思想是將數組按照一定的增量（gap）分成若干個子序列，對每個子序列進行插入排序。隨著增量的逐漸減小，子序列的長度逐漸變短，最終當增量為1時，整個數組就變成了一個子序列，此時進行最后一次插入排序，數組就變得有序了。

希爾排序的實現步驟

1. 選擇增量序列：希爾排序的關鍵在于選擇合適的增量序列。常見的增量序列有希爾增量（gap = n/2, gap = gap/2）、Hibbard增量（gap = 2^k - 1）等。本文以希爾增量為例。

2. 分組插入排序：根據當前增量將數組分成若干個子序列，對每個子序列進行插入排序。

3. 縮小增量：逐步縮小增量，重復步驟2，直到增量為1。

4. 最后一次插入排序：當增量為1時，對整個數組進行一次插入排序，排序完成。

Python實現希爾排序

下面是一個使用Python實現希爾排序的示例代碼：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 對子序列進行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 縮小增量

    return arr

# 示例
arr = [12, 34, 54, 2, 3]
print("排序前:", arr)
sorted_arr = shell_sort(arr)
print("排序后:", sorted_arr)

代碼解析

• gap = n // 2：初始增量為數組長度的一半。
• while gap > 0：當增量大于0時，繼續排序。
• for i in range(gap, n)：從增量位置開始，對每個子序列進行插入排序。
• while j >= gap and arr[j - gap] > temp：在子序列中進行插入排序，將較大的元素向后移動。
• gap //= 2：每次循環后，縮小增量。

示例輸出

排序前: [12, 34, 54, 2, 3]
排序后: [2, 3, 12, 34, 54]

希爾排序的時間復雜度

希爾排序的時間復雜度取決于增量序列的選擇。對于希爾增量序列，最壞情況下的時間復雜度為O(n^2)，但對于某些增量序列（如Hibbard增量），時間復雜度可以降低到O(n^(³⁄₂))。希爾排序的平均時間復雜度通常被認為是O(n log n)。

總結

希爾排序是一種改進的插入排序算法，通過逐步縮小增量來使得數組逐漸趨于有序。雖然它的時間復雜度不如快速排序或歸并排序那樣優秀，但在某些特定情況下，希爾排序仍然是一個不錯的選擇。通過選擇合適的增量序列，可以進一步提高希爾排序的性能。