Shel算法描述 void ShellSort(SqList &l& #for(d=Llength /2: d>=1; d=d/2) 结 for(i=d+1;i<= Length;i++)∥完成一趟She排序 if(L. r. key<L.rid]key){/寻找插入位置 Lr10=Lrli;暂存 for(j=i-d j>0&&L.rIO. key<Lrli.key: j-=d) 部 L rl j+d I=L.rjl;∥数据向后搬移 Lrj+dl=Lr|0;/插入 序 3/ShellSort end 2性能分析;时间复杂度:Om3;空间复杂度:O She排序方法不稳定; 一趟Shel排序算法的另一种描述 s* void ShellInsert(SqList &L, int d) 结for(k=1;k<=d;k+)∥(d,d组子序列分别排序 构 for(i=d+k; i<=L length; i+=di //o(n/d forGj=i-d: j>0 && e key<. rIj.key ;j-=d) rj+d|= Lrlj:;∥o(nd∥ L rlj+d=e; 排 3// O(n*n/d void ShellSort(sqlist &L, int detal, int t) for(k=0; k<t; k++)Shelllnsert(L, dIta kD; ∥O(ogn)14 数 据 结 构 之 内 部 排 序 27 Shell算法描述 void ShellSort(SqList &L){ for(d=L.length /2 ; d>=1 ; d=d/2) for(i=d+1; i<=L.length;i++) //完成一趟Shell 排序 if(L.r[i].key<L.r[i-d].key){// 寻找插入位置 L.r[0]=L.r[i]; //暂存 for(j=i-d ; j>0&&L.r[0].key<L.r[j].key ; j-=d) L.r[ j+d ]=L.r[ j ]; //数据向后搬移 L.r[ j+d ]=L.r[0]; //插入 } } //ShellSort end 性能分析：时间复杂度：O(n )；空间复杂度：O(1)； Shell 排序方法不稳定； 3/2 数 据 结 构 之 内 部 排 序 28 一趟Shell排序算法的另一种描述 void ShellInsert(SqList &L , int d){ for(k=1 ; k<=d ; k++) //O(d), d组子序列分别排序 for(i=d+k ; i<=L.length ; i+=d){ //O( n / d ) e=L.r[i] ; for(j=i-d ; j>0 && e. key<L.r[j].key ; j-=d) L.r[ j+d ]=L.r[ j ]; //O(n/d)// L.r[j+d]=e ; } }// O(n*n/d) void ShellSort(SqList &L , int dlta[] , int t ){ for(k=0; k<t; k++) ShellInsert(L,dlta[k]); }// O(log n)