4.5　希爾排序算法

希爾排序法是插入排序法的一種高級改進版本。希爾排序法可以減少插入排序法中數據移動的次數，加快排序進程，因此又被稱為縮小增量排序法。

希爾排序法的基本思想是：將原始數據分成特定間隔的幾組數據，然后使用插入排序法對每組數據進行排序，排序后再減小間隔距離，重復插入法對每組數據排序，直到所有數據完成排序為止。

例如，有一組數據：60, 82, 17, 35, 52, 73, 54, 9，如圖4.33所示。采用希爾排序算法對其遞增排序，步驟如下。

（1）原數列中有8個數據，將間隔數設置為8/2=4位，即每間隔4位的數據為一組，共分為4組，數列1為60, 52，數列2為82, 73，數列3為17, 54，數列4為35, 9，圖4.34所示。

（2）將每個數列內的元素按照左小右大的原則進行排序，最后得到的數列1為52, 60，數列2為73, 82，數列3為17, 54，數列4為9, 35。第一次排序結果如圖4.35所示。

（3）縮小間隔數為2位，即將原數列間隔2位的數據為一組，共分為兩組數列，數列1為52, 17,60, 54，數列2為73, 9, 82, 35，如圖4.36所示。

（4）對每個數列內的元素從小到大進行排序，位置錯誤的元素進行交換，最后得到的數列1為17, 52, 54, 60，數列2為9, 35, 73, 82。第二次排序結果如圖4.37所示。

（5）繼續縮小間隔數為1位，對圖4.37中的元素進行排序，最后的排序結果如圖4.38所示。

【實例4.9】　使用希爾排序法將列表中的數字遞增排序。（實例位置：資源包\Code\04\09）

用Python代碼實現上方示例中的希爾排序算法，具體代碼如下：

運行結果如圖4.39所示。

【實例4.10】　新聞頭條。（實例位置：資源包\Code\04\10）

每天都會有各種各樣的新聞發生，點擊率較高的新聞就會成為新聞頭條。編寫程序，利用希爾排序法，根據新聞的點擊率對新聞標題進行排序。具體的Python代碼如下：

運行結果如圖4.40所示。