希爾排序(Shell’s Sort)又稱“縮小增量排序”(Diminishing Increment Sort),它也是一種屬插入排序類的方法,但在時間效率上較前述幾種排序方法有較大的改進。
從對直接插人排序的分析得知,其算法時間復雜度為O(n),但是,若待排記錄序列為“正序”時,其時間復雜度可提高至O(n)。由此可設想,若待排記錄序列按關鍵字“基本有序”,即序列中具有下列特性
的記錄較少時,直接插人排序的效率就可大大提高,從另一方面來看,由於直接插人排序算法簡單,則在n值很小時效率也比較高。希爾排序正是從這兩點分析出發對直接插人排序進行改進得到的一種插入排序方法。
它的基本思想是:先將整個待排記錄序列分割成為若幹子序列分別進行直接插人排序,待整個序列中的記錄“基本有序”時,再對全體記錄進行一次直接插入排序。
仍以式(10-4)中的關鍵字為例,先看一下希爾排序的過程。初始關鍵字序列如圖1的第1行所示。首先將該序列分成5個子序列{R_{1},R_{6}}，{ R_{2},R_{7} }，···，{ R_{5},R_{10} },如圖1的第2行至第6行所示,分別對每個子序列進行直接插入排序,排序結果如圖1的第7行所示,從第1行的初始序列得到第7行的序列的過程稱為一趟希爾排序。然後進行第二趟希爾排序,即分別對下列3個子序列:{ R_{1},R_{4},R_{7},R_{10}}，{ R_{ 2},R_{5},R_{8} }和{ R_{3},R_{6},R_{9} }進行直接插人排序,其結果如圖1的第11行所示,最後對整個序列進行一趟直接插入排序。至此,希爾排序結束,整個序列的記錄已按關鍵字非遞減有序排列。
圖1 希爾排序示例
從上述排序過程可見,希爾排序的一個特點是:子序列的構成不是簡單地“逐段分割”,而是將相隔某個“增量”的記錄組成一個子序列。如上例中,第一趟排序時的增量為5,第二趟排序時的增量為3,由於在前兩趟的插入排序中記錄的關鍵字是和同–子序列中的前一個記錄的關鍵字進行比較,因此關鍵字較小的記錄就不是一步一步地往前挪動，而是跳躍式地往前移,從而使得在進行最後一趟增量為1的插入排序時,序列已基本有序,隻要作記錄的少量比較和移動即可完成排序,因此希爾排序的時間復雜度較直接插入排序低。下面用算法語言描述上述希爾排序的過程,為此先將算法1.1改寫成如算法1.2所示的一般形式。希爾排序算法如算法1.3所示.
算法1.1
算法1.2算法 1.3
希爾排序的分析是一個復雜的問題,因為它的時間是所取“增量”序列的函數,這涉及一些數學上尚未解決的難題。因此,到目前為止尚未有人求得一種最好的增量序列,但大量的研究已得出一些局部的結論。如有人指出,當增量序列為dlta[k]= 2^{t-k+1}-1時,希爾排序的時間復雜度為O( n^{3/2} ),其中t為排序趟數,1≤k≤t≤ left lfloor log_{2}(n+1) right rfloor 。還有人在大量的實驗基礎上推出:當n在某個特定范圍內,希爾排序所需的比較和移動次數約為 n^{1.3} ,當n→∞時,可減少到n( log_{2}n ) 2^{[2]} 。增量序列可以有各種取法,但需註意:應使增量序列中的值沒有除1之外的公因子,並且最後一個增量值必須等於1。