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