#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void SH(long a[], long n)/*SHELL（希爾）排序。將數(shù)組分成h個(gè)子表，子表中相鄰兩個(gè)元素下標(biāo)相差h。
                             每個(gè)子表中進(jìn)行直接插入排序。不斷減小h，直到完成排序*/
{
long j,i,t,k,h;
for(h=n/2;h>=1;h=h/2)
	for(i=0;i<h;i++)
	{
	 for(j=i+h;j<n;j=j+h)
	 {t=a[j];
	  k=j-h;
	  while(k>=0&&t<a[k])
	  {
	   a[k+h]=a[k]; 
	   k=k-h;
	  }
	  a[k+h]=t;
	 }
	}
}	       
	   
void main()
{
long i,a[100000],n;
clock_t t1,t2;
double time;
scanf("%d",&n);
for(i=0;i<n;i++)
a[i]=rand();
t1=clock();
SH(a,n);
t2=clock();
time=(double)(t2-t1)/CLK_TCK;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("%f",time);
}