啪啪拉拉噼里啪啦

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

希爾排序基本思想

  基本思想：
　    先取一個小于n的整數(shù)d₁作為第一個增量，把文件的全部記錄分成d₁個組。所有距離為d_l的倍數(shù)的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d₂<d₁重復上述的分組和排序，直至所取的增量d_t=1(d_t<d_t-l<…<d₂<d₁)，即所有記錄放在同一組中進行直接插入排序為止。
    　該方法實質上是一種分組插入方法。

給定實例的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基本一致，只是由于沒有哨兵而在內循環(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²的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n²)差別不大。
　　③在希爾排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內直接插入較快，后來增量d_i逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按d_i-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。
    　因此，希爾排序在效率上較直接插人排序有較大的改進。

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