如何利用Python編寫希爾排序演算法？

如何利用Python寫希爾排序演算法？

希爾排序（Shell Sort）是一種改進的插入排序演算法，它透過比較相距一定間隔的元素來移動元素，從而減少了移動的次數。希爾排序的核心思想是將待排序的元素按照一定的間隔分組，然後對每個分組進行插入排序，不斷縮小間隔直至為1，最後再進行一次完整的插入排序。

下面我們將詳細介紹如何利用Python來寫希爾排序演算法。

首先，我們需要寫一個函數來實作插入排序。插入排序的核心思想是將目前元素插入已經排好序的前面的序列中。

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

接下來，我們寫一個希爾排序函數，該函數接收一個待排序的清單作為參數。

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 = gap // 2  # 缩小间隔

最後，我們寫一個測試函數來驗證希爾排序的正確性。

def test_shell_sort():
    arr = [12, 34, 55, 23, 8, 17, 45, 91]
    shell_sort(arr)
    assert arr == [8, 12, 17, 23, 34, 45, 55, 91]
    print("希尔排序测试通过！")

if __name__ == "__main__":
    test_shell_sort()

運行測試函數後，如果沒有報錯並輸出了"希爾排序測試通過！"的提示，則表示希爾排序的實現是正確的。

希爾排序的時間複雜度與選取的間隔序列有關，目前還沒有求得一個最好的間隔序列。希爾排序的平均時間複雜度約為O(n^1.3)，最壞情況下的時間複雜度約為O(n^2)。

希爾排序是一種高效的排序演算法，相比於插入排序，它可以在一開始就使插入排序的元素部分有序，從而減少了後續的比較和移動操作，提高了排序的效率。如果想要快速地對一個清單進行排序，不妨嘗試使用希爾排序演算法。

以上是如何利用Python編寫希爾排序演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！