#include<iostream>
using namespace std;
/*
*希尔排序也是缩小增量排序，其时间复杂度较插入排序要好，因为在最后进行插入排序之前已经基本有序了；
*插入排序的时间复杂度为O(n^2),而希尔排序能缩小到O(n^3/2)
*/
//template <class T>//模版传递指针和数组需注意
//void shell_sort(const *arr(T),const T &n,const T &delt_up,const int &i){
//模版传递指针，数组遇到问题，希望高人指点
void shell_sort(int *arr,int n,int delt_up[],int i){
//此处相当于插入排序，只是间隔变为delt_up[i];
for(int j=delt_up[i];j<n;j++){
int temp=arr[j];
int m=j-delt_up[i];
while(arr[m]>temp&&m>=0){
arr[m+delt_up[i]]=arr[m];
m=m-delt_up[i];
}
arr[m+delt_up[i]]=temp;
}
}
int main(int argc,char *argv[]){
int m=3;//增量个数
int delt_up[]={1,3,5};//增量数组
int n,i;
cin>>n;
int *arr=new int[n];//存放待排序列
for(i=0;i<n;i++){
cin>>arr[i];
}
for(i=0;i<m;i++){
shell_sort(arr,n,delt_up,i);
}
for(i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}