哈希排序

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000009];
inline void read(register int &a)
{
    a=0;char c;
    while((c=getchar())<48);
    do a=(a<<3)+(a<<1)+(c^48);
    while((c=getchar())>47);
} 
void write(int x)
{
	if(x < 10) putchar(x | 48);
	else write(x / 10), putchar(x % 10 | 48);
}
signed main(){
	scanf("%ld",&n);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=sqrt(n);i>=1;i/=2){
		for(int i1=i+1;i1<=n;++i1){
        	int cmp=a[i1];
        	int j=i1-i;
        	while(j>=0&&cmp<a[j]){
            	a[j+i]=a[j];
            	j-=i;
            	}
        	a[j+i]=cmp;
    	}
	}
	for(int i=1;i<=n-1;++i) write(a[i]), (i < n && putchar(' ')); 
	write(a[n]);
//	cout<<endl<<clock();
	return 0;
}