希爾排序(Shell Sort)是插入排序的一種。因D．L．Shell于1959年提出而得名。
希爾排序基本思想
基本思想：
先取一個小于n的整數(shù)d
1作為第一個增量，把文件的全部記錄分成d
1個組。所有距離為d
l的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d
2<d
1重復上述的分組和排序，直至所取的增量d
t=1(d
t<d
t-l<…<d
2<d
1)，即所有記錄放在同一組中進行直接插入排序為止。
該方法實質(zhì)上是一種分組插入方法。
給定實例的shell排序的排序過程
假設待排序文件有10個記錄，其關鍵字分別是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次為：
5，3，1
排序過程如【
動畫模擬演示】。
Shell排序的算法實現(xiàn)
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基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標越界。
2．設監(jiān)視哨的shell排序算法 具體算法【參考書目[12] 】
算法分析
1．增量序列的選擇 Shell排序的執(zhí)行時間依賴于增量序列。
好的增量序列的共同特征：
① 最后一個增量必須為1；
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。
有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數(shù)約在n
l.25到1.6n
1.25之間。
2．Shell排序的時間性能優(yōu)于直接插入排序 希爾排序的時間性能優(yōu)于直接插入排序的原因：
①當文件初態(tài)基本有序時直接插入排序所需的比較和移動次數(shù)均較少。
②當n值較小時，n和n
2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n
2)差別不大。
③在希爾排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量d
i逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按d
i-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。
因此，希爾排序在效率上較直接插人排序有較大的改進。
3．穩(wěn)定性 希爾排序是不穩(wěn)定的。參見上述實例，該例中兩個相同關鍵字49在排序前后的相對次序發(fā)生了變化。