希爾排序

希爾排序，又稱作Shell Sort，也叫縮小增量排序演算法，是前文講解的插入排序更高效的一種排序演算法，

其原理是：在n個元素的串列里，取增量n/2，數列開始值與增量值的尾值進行比較，小的放前面，大的放后面；把增量的前后都比較一遍，然后增量數-1，

繼續從頭到尾進行比較，并調整大小；一直到增量等于1，就完成了所有串列元素的排序，至于增量規則可以自行定義，

圖解寫入排序

假設，又一個串列為[8,0,4,3,2,1]，具體原理步驟如下：

第1次，增量為3，那么需要進行3次回圈，（每次回圈2個數進行比較排序）

增量3
上面，首先對索引0到索引3的數值進行比較，然后比較索引1與索引4，最后比較索引2與索引5的值，

第2次，增量為2，那么需要進行2次回圈，

增量2
接著，對索引0、索引2、與索引4的數值進行比較，然后比較索引1、索引3、索引5的數值，

第3次，增量為1，那么需要進行1次回圈，

增量1
最后，對比索引0與索引1，索引1與索引2，索引2與索引3，索引3與索引4，索引4與索引5的各個數的值，就完成了最終的排序程序，這個程序就叫希爾排序，

實戰：希爾排序

通過上面的舉例，以及圖解的分析，相信讀者都能夠看懂希爾排序的程序以及相對應的原理，下面，我們來用Python實作希爾排序，示例如下：

def shell_sort(my_list):
    n = len(my_list)
    if n == 1:
        return my_list
    space = int(n / 2)
    while space > 0:
        for i in range(space, n):
            temp = my_list[i]
            j = i
            while j >= space and my_list[j - space] > temp:
                my_list[j] = my_list[j - space]
                j -= space
            my_list[j] = temp
        space = int(space / 2)
    return my_list


if __name__ == "__main__":
    my_list = [8, 0, 4, 3, 2, 1]
    print("排序前的陣列：", my_list)
    print("排序后的陣列：", shell_sort(my_list))

運行之后，效果如下所示：

最終效果

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297585.html

標籤：python

上一篇：Python模擬登陸教務系統爬取成績資訊+繪制成績分布圖+匯入MySQL

下一篇：對反游戲外掛技術的思考及實作

Python資料結構與演算法（15）---希爾排序

目錄

希爾排序

圖解寫入排序

實戰：希爾排序