本節(jié)介紹第二種插入排序方法：希爾排序。

希爾排序(Shell Sort)是插入排序的一種。因 D.L.Shell 于 1959 年提出而得名。

希爾排序基本思想

基本思想：

先取一個小于 n 的整數(shù) d1 作為第一個增量，把文件的全部記錄分成 d1 個組。所有距離為 d1 的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量 d2<d1 重復(fù)上述的分組和排序，直至所取的增量 dt=1(dt<dt-1<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

該方法實質(zhì)上是一種分組插入方法。

給定實例的 shell 排序的排序過程

假設(shè)待排序文件有 10 個記錄，其關(guān)鍵字分別是：

49，38，65，97，76，13，27，49，55，04。

增量序列的取值依次為：

5，3，1

排序過程如【動畫模擬演示】。

Shell 排序的算法實現(xiàn)

1．不設(shè)監(jiān)視哨的算法描述

void ShellPass(SeqList R，int d)  
 {//希爾排序中的一趟排序，d為當(dāng)前增量  
   for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū)  
     if(R[i].key<R[i-d].key){  
       R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵  
       do {//查找R[i]的插入位置  
          R[j+d]；=R[j]； //后移記錄  
          j=j-d； //查找前一記錄  
       }while(j>0&&R[0].key<R[j].key)；  
       R[j+d]=R[0]； //插入R[i]到正確的位置上  
     } //endif  
 } //ShellPass  

void  ShellSort(SeqList R)  
 {  
  int increment=n； //增量初值，不妨設(shè)n>0  
  do {  
        increment=increment/3+1； //求下一增量  
        ShellPass(R，increment)； //一趟增量為increment的Shell插入排序  
     }while(increment>1)  
  } //ShellSort  

注意： 當(dāng)增量 d=1 時，ShellPass 和 InsertSort 基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標(biāo)越界。

算法分析

1．增量序列的選擇

Shell 排序的執(zhí)行時間依賴于增量序列。

好的增量序列的共同特征：

• 最后一個增量必須為 1；
• 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。

有人通過大量的實驗，給出了目前較好的結(jié)果：當(dāng)n較大時，比較和移動的次數(shù)約在n^l.25到1.6n^1.25之間。

2．Shell 排序的時間性能優(yōu)于直接插入排序

希爾排序的時間性能優(yōu)于直接插入排序的原因：

• 當(dāng)文件初態(tài)基本有序時直接插入排序所需的比較和移動次數(shù)均較少。
• 當(dāng) n 值較小時，n 和 n2 的差別也較小，即直接插入排序的最好時間復(fù)雜度 O(n)和最壞時間復(fù)雜度 0(n2)差別不大。
• 在希爾排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量 di 逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。

因此，希爾排序在效率上較直接插人排序有較大的改進。

3．穩(wěn)定性

希爾排序是不穩(wěn)定的。參見上述實例，該例中兩個相同關(guān)鍵字 49 在排序前后的相對次序發(fā)生了變化。