从0开始学算法--排序（1.4希尔排序）

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;

const int maxn=1e5+1;
long long cnt;
int l;
int A[maxn]
int n;
vector<int >G;

//指定间隔g的篡改人排序
void insertionSort(int A[],int n,int g){
    for(int i=g;i<n;i++){
        int v=a[i];
        int j=i-g;
        while(j>=0&&a[j]>v){
            A[j+g]=a[j];
            j-=g;
            cnt++;
        }
        A[j+g]=v;
    }
}

void shellSort(int A[],int n){
    //生成数列1，4，13，40，121，364，1093
    for(int h=1;;){
        if(h>n)break;
        G.push_back(h);
        h=3*h+1;
    }
    
    for(int i=G.size()-1;i>=0;i--){//逆序指定g
        insertionSort(A,n,G[i]);
    }
}

int main(){
    scanf("%d",&n);
    
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }
    cnt=0;
    
    shellSort(A,n);
    
    for(int i=G.size()-1;i>=0;i--){
        printf("%d",G[i]);
        if(i)printf(" ");
    }
    printf("\n");
    printf("%d\n",cnt);
    for(int i=0;i<n;i++){
        printf("%d\n",a[i]);
    }
    
    return 0;
}