曆史
希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由1959年公布。一些老版本教科書和參考手冊把該算法命名為Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根據Metzner本人的說法，“我沒有為這種算法做任何事，我的名字不應該出現在算法的名字中。”
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。但插入排序一般來說是低效的，因為插入排序每次隻能将數據移動一位。
基本思想
先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組内進行直接插人排序；然後，取第二個增量d2，該方法實質上是一種分組插入方法。
應用
實時調度策略中,EDF算法應用最為廣泛,但其在系統過載的情況下,僅由任務截止期決定任務執行順序,使得截止期錯失率非常高,且系統收益小。近年來,出現了一些改進的EDF算法,綜合考慮了時間和執行價值,但未加入能量因素,對于能量有限的系統,充分利用能量是極其重要的。
針對這一問題,提出一種基于希爾排序的動态優先級調度算法,在系統過載時,綜合考慮任務截止時間、執行價值、消耗能量三種因素确定任務優先級,通過希爾排序算法選出優先級高的任務加入優先調度子集,進行率先調度。實驗結果表明,該算法不僅能降低任務截止期錯失率,還能提高系統執行收益。
