软考软件设计师专题讲义九：数据结构相关算法

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

　　希尔排序又称缩小增量排序，是1959年由D.L.Shell提出来的，较前述几种插入排序方法有较大的改进。

　　直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。

　　希尔排序方法：

　　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]; /*为统一算法设置监测*/

　　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。希尔排序方法是一个不稳定的排序方法。

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总