文章目录
- 1.希尔排序(缩小增量法)
- 2.排序过程
- 3.最坏复杂度分析
1.希尔排序(缩小增量法)
- 基本思想：
分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。
-
对待排记录序列先作“宏观”调整，再作“微观”调整。
“宏观”调整，指的是，“跳跃式”的插入排序。
2.排序过程
- 首先将记录序列分成若干子序列，
- 然后分别对每个子序列进行直接插入排序，
- 最后待基本有序时，再进行一次直接插入排序
- 例如：将 n 个记录分成 d 个子序列：
d个数据分为1组
{ R[1]， R[1+d]， R[1+2d]， …， R[1+kd] }
{ R[2]， R[2+d]， R[2+2d]， …， R[2+kd] }
…
{ R[d]， R[2d]， R[3d]， …， R[kd]， R[(k+1)d] }
其中， d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。
- 例 初始： 49 38 65 97 76 13 27 48 55 4
- 代码
//r是待排序的记录，d是增量序列，一共有T个
void shellsort(JD r[], int n, in d[], int T)
{
int i,j,k;
JD x;
k=0;
//循环每一趟进行分组，组内进行简单插入排序
while(k {
//i为未排序记录的位置
for (i=d[k]+1;i {
x=r[i];
j=i-d[k];
//j为本组i前面的记录位置
while ((j>0)&&(x.key {
//组内简单插入排序
r[j+d[k]]=r[j];
j=j-d[k];
}
r[j+d[k]]=x;
}
k++;
}
}
3.最坏复杂度分析
- 定理： 使用希尔增量的最坏时间复杂度为 O(
).
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
