Posted on 2006-06-13 22:26
Enjoy Life 阅读(838)
评论(0) 编辑 收藏 引用 所属分类:
DS study
void ShellInsert(SqList &L, int dk){
//对顺序表L作一趟希尔插入排序，本算法是和一趟直接插入排序相比，做了以下修改：
// 1、前后记录位置的增量是dk，而不是1；
// 2、r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到
for(i=dk+1; i<=L.length; ++1){
if(LT(L.r[i].key, L.r[i-dk].key)){//需将L.r[i]插入有序增量子表中
L.r[0] = L.r[i]; //暂存在L.r[0]
for(j=i-dk; j>0 && LT(L.r[0].key, L.[j].key); j-=dk)
L.r[j+dk] = L.r[j];//记录后移，查找插入位置
L.r[j+dk] = L.r[0];//插入
}
}
}//ShellInsert
void ShellSort(SqList &L, int dlta[], int t){
//增量序列dlta[0...t-1]对顺序表L作希尔排序
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
}//ShellSort