希尔排序

算法思想：通过划分增量，来进行插入排序，可以搭配直接插入排序或者是折半插入排序。
本质上是把n个数划为了 d=n/k 个序列 依次遍历使得有序，再逐渐减少增量 d 的大小，使得最终增量为1，最终使得数列基本有序，从而提升算法的效率

时间复杂度

可以达到 O(n^1.3)

希尔(直接插入排序)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int q[N];
int n;
void shell_sort()
{
    for(int d=n/3; d; d=d==2? 1 : d/3)  // 规定增量为n/3时，可以使得时间复杂度达到O(n^1.3) 注意当n=2时无法除3，直接令其为1
    {
      for(int start=0 ; start < d ; start++) // 因为对n进行了划分，使得划分后一定有 d个(n/3个) 以 d 为增量的序列，依次遍历三个序列，使其递增有序(即会有d个序列)

      // 有n个数，除以k , 会有 n/k 个序列，每个序列 k 个元素。 故只需遍历d个序列 
      {
          for(int i=start+d; i<n ; i+=d) //每个序列都以d为增量，把每个序列进行直接插入排序
          {
              int t=q[i],j=i;
              while(j>start&&q[j-d]>t) // 注意j > start 避免遍历前面序列
              {
              q[j]=q[j-d];
              j-=d;
              }
            q[j]=t;
          }
      }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin >> q[i];

    shell_sort();

    for(int i=0;i<n;i++) cout << q[i] << ' ';
    return 0;
}