軟考軟件設(shè)計(jì)師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

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

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

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

　　希爾排序方法：

　　1. 選擇一個(gè)步長(zhǎng)序列t1，t2，…，tk，其中ti>tj，tk=1;

　　2. 按步長(zhǎng)序列個(gè)數(shù)k，對(duì)序列進(jìn)行k趟排序;

　　3. 每趟排序，根據(jù)對(duì)應(yīng)的步長(zhǎng)ti，將待排序列分割成若干長(zhǎng)度為m的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅步長(zhǎng)因子為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

　　【算法10.5】

　　void ShellInsert(S_TBL &p，int dk)

　　{ /*一趟增量為dk的插入排序，dk為步長(zhǎng)因子*/

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

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

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

　　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]對(duì)順序表*p作希爾排序*/

　　for(k=0;k

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

　　}

　　【時(shí)效分析】

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

　　　　　　　計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總