（2.7）希尔排序

文章目录

• ​​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 < T)
  {
    //i为未排序记录的位置
    for (i=d[k]+1;i<=n;i++)
    {
      x=r[i];
      j=i-d[k];
      //j为本组i前面的记录位置
      while ((j>0)&&(x.key<r[j].key))
      {
        //组内简单插入排序
        r[j+d[k]]=r[j];
        j=j-d[k];
      }
      r[j+d[k]]=x;
    }
    k++;
  } 
}

3.最坏复杂度分析

• 定理： 使用希尔增量的最坏时间复杂度为 O( ).