posts - 63, comments - 37, trackbacks - 0, articles - 0
  IT博客 :: 首页 :: 新随笔 :: 联系 ::  :: 管理

希尔排序算法描述

Posted on 2006-06-13 22:26 Enjoy Life 阅读(826) 评论(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

只有注册用户登录后才能发表评论。