希爾排序

希爾排序是插入排序的一種（分組+直接插入排序）

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

void shellpass(seqlist r，int d)  

  {//希爾排序中的一趟排序，d為目前增量  

    for(i=d+i;i<=n；i++) //将r[d+1．．n]分别插入各組目前的有序區  

      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  

二 算法分析

算法分析

1．增量序列的選擇

shell排序的執行時間依賴于增量序列。

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

① 最後一個增量必須為1；

② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。

2．shell排序的時間性能優于直接插入排序

希爾排序的時間性能優于直接插入排序的原因：

①當檔案初态基本有序時直接插入排序所需的比較和移動次數均較少。

②當n值較小時，n和n2的差别也較小，即直接插入排序的最好時間複雜度o(n)和最壞時間複雜度0(n2)差别不大。

③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組内直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使檔案較接近于有序狀态，是以新的一趟排序過程也較快。

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

3．穩定性

希爾排序是不穩定的。參見上述執行個體，該例中兩個相同關鍵字49在排序前後的相對次序發生了變化。

轉載：http://blog.csdn.net/xsf50717/article/details/40345625