Shell Sort

Shellsort, also known as Shell sort or Shell’s method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).[3] The method starts by sorting pairs of elements far apart from each o ther, then progressively reducing the gap between elements to be compared. By starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959.[4][5] The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem. ——From Wikimedia

对于希尔排序的渐小增量d，可以理解为每组相同d的data独立出来作为一个新的子表进行直接插入排序，也可以理解为在整个数组中，有一个跳跃指针在进行自身递减的遍历运动。

20140912155122!Sorting_shellsort_anim

跳跃遍历，d是多少看不出来，太快了

Sorting_shellsort_anim

同上

1345862-20200606234720190-975139218

还算形象的一个

void shell_Sort(int A[],int n){
  
	int d,i,j;
  //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
  //label1:
  for(d = n/2;d>=1;d=d/2)//步长变化
    //label2:
    for(i=d+1;i<=n;++i)//i=d+1保证配对成组，++i从下一个同d的子表开始，直到i=n结束
      if(A[i]<A[i-d]){//将A[i]插入到有序增量子表。子表后一个与前一个比较
        A[0]=A[i]//暂存在A[0]中
        //label3：
          for(j=i-d;j>0 && A[0]<A[j];j-=d)//j-=d查找子表中有木有前一个元素
          A[j+d]=A[j];//记录后移，查找插入的位置
        A[j+d]=A[0];//插入
      }//if
  
}