（2.7）希尔排序

本文主要是介绍（2.7）希尔排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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( $N^2$ ).
  

这篇关于（2.7）希尔排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---