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

該方法實質上是一種分組插入方法。

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

假設待排序文件有 10 個記錄，其關鍵字分別是：

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

增量序列的取值依次為：

5，3，1

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

Shell 排序的算法實現

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

void ShellPass(SeqList R，int d)  
 {//希爾排序中的一趟排序，d為當前增量  
   for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當前的有序區(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； //增量初值，不妨設n>0  
  do {  
        increment=increment/3+1； //求下一增量  
        ShellPass(R，increment)； //一趟增量為increment的Shell插入排序  
     }while(increment>1)  
  } //ShellSort

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

算法分析

1．增量序列的選擇

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

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

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

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

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

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

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

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

3．穩(wěn)定性

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