希爾排序(Shell Sort)是插入排序的一種
希爾排序基本思想
基本思想
先取一個小於n的整數d
先在各組內進行直接插人排序;然後 2 該方法實質上是一種分組插入方法。 給定實例的shell排序的排序過程 假設待排序文件有10個記錄，其關鍵字分別是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次為： 5，3，1 排序過程如【 動畫模擬演示 】。 Shell排序的算法實現 1. 不設監視哨的算法描述 void ShellPass(SeqList R，int d) {//希爾排序中的一趟排序，d為當前增量 for(i=d+1;i<=n;i++) //將R[d+1..n]分別插入各組當前的有序區 if(R[i].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+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基本一致，只是由於沒有哨兵而在內循環中增加了一個循環判定條件"j>0"，以防下標越 界。 2.設監視哨的shell排序算法 具體算法【參考書目[12] 】 算法分析 1.增量序列的選擇 Shell排序的執行時間依賴於增量序列。 好的增量序列的共同特征： ① 最後一個增量必須為1; ② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。 有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在n l.25 到1.6n 1.25 之間。 2.Shell排序的時間性能優於直接插入排序 希爾排序的時間性能優於直接插入排序的原因： ①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。 ②當n值較小時，n和n 2 的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n 2 )差別不大。 ③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量d i 逐漸縮小，分組數逐漸 減少，而各組的記錄數目逐漸增多，但由於已經按d i-1 作為距離排過序，使文件較接近於有序狀態，所以新的一趟排序過程也較快 因此，希爾排序在效率上較直接插人排序有較大的改進。 3.穩定性 希爾排序是不穩定的。參見上述實例，該例中兩個相同關鍵字49在排序前後的相對次序發生了變化。
From:http://tw.wingwit.com/Article/program/sjjg/201311/23805.html