軟考軟件設計師專題講義九：數據結構相關算法

　　希爾排序(Shell’s Sort)算法分析：

　　希爾排序又稱縮小增量排序，是1959年由D.L.Shell提出來的，較前述幾種插入排序方法有較大的改進。

　　直接插入排序算法簡單，在n值較小時，效率比較高，在n值很大時，若序列按關鍵碼基本有序，效率依然較高，其時間效率可提高到O(n)。希爾排序即是從這兩點出發(fā)，給出插入排序的改進方法。

　　希爾排序方法：

　　1. 選擇一個步長序列t1，t2，…，tk，其中ti>tj，tk=1;

　　2. 按步長序列個數k，對序列進行k趟排序;

　　3. 每趟排序，根據對應的步長ti，將待排序列分割成若干長度為m的子序列，分別對各子表進行直接插入排序。僅步長因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。

　　【算法10.5】

　　void ShellInsert(S_TBL &p，int dk)

　　{ /*一趟增量為dk的插入排序，dk為步長因子*/

　　for(i=dk+1;i<=p->length;i++)

　　if(p->elem[i].key < p->elem[i-dk].key) /*小于時，需elem[i]將插入有序表*/

　　{ p->elem[0]=p->elem[i]; /*為統一算法設置監(jiān)測*/

　　for(j=i-dk;j>0&&p->elem[0].key < p->elem[j].key;j=j-dk)

　　p->elem[j+dk]=p->elem[j]; /*記錄后移*/

　　p->elem[j+dk]=p->elem[0]; /*插入到正確位置*/

　　}

　　}

　　void ShellSort(S_TBL *p，int dlta[]，int t)

　　{ /*按增量序列dlta[0，1…，t-1]對順序表*p作希爾排序*/

　　for(k=0;k

　　ShellSort(p，dlta[k]); /*一趟增量為dlta[k]的插入排序*/

　　}

　　【時效分析】

　　希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于步長因子序列的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的步長因子序列的方法。步長因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：步長因子中除1外沒有公因子，且最后一個步長因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總