一、 希尔排序（Shell Sort）

• 希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序
• 希尔排序：先将待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

（一）希尔排序

1. 增量d=4的希尔排序

• 希尔排序，第一趟：
  
  
  
  
• 希尔排序，第二趟：
  
  
  
• 希尔排序，第三趟：
  
  
• 希尔排序整体步骤：
  

2. 增量d=4的希尔排序

（二）算法实现

//希尔排序
void ShellSort(int A[], int n){int d,i,j;//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到for(d=n/2 ; d>=1 ; d=d/2){	//步长变化for(i=d+1 ; i<=n ; ++i){if(A[i]<A[i-d]){	//需要将A[i]插入有序增量子表A[0]=A[i];		//暂存在A[0]for(j=i-d ; j>0&&A[0]<A[j] ; j-=d){A[j+d]=A[j];//记录后移，查找插入的位置}A[j+d]=A[0];	//插入}}}
}

（三）算法时间复杂度

（四）算法性能分析

• 适用性：仅适用于顺序表，不适用于链表