#include <bits/stdc++.h> using namespace std;
#define MAXSIZE 200000
typedef int KeyType;
typedef struct {
KeyType key;
}RedType;
typedef struct {
RedType r[MAXSIZE + ];
int length;
}SqList;
int Random(int start, int end){
int dis = end - start;
return rand() % dis + start;
}
void ShellInsert(SqList &L,int dk) {
int i, j;
for (i = dk + ; i <= L.length; ++i)
if(L.r[i].key < L.r[i - dk].key) {
L.r[] = L.r[i];
for (j = i - dk; j > && L.r[].key < L.r[j].key; j -= dk)
L.r[j + dk] = L.r[j];
L.r[j + dk] = L.r[];
}
}
void ShellSort (SqList &L, int dt[], int t) {
double start_time, finish_time, cord_time;
start_time = clock();
int k;
for (k = ; k < t; ++k) {
ShellInsert(L, dt[k]);
}
finish_time = clock();
cord_time = (double)(finish_time - start_time) ;
printf("ShellSort time=%f ms\n", cord_time);
// int i;
// for (i = 0; i < 3; ++i)
// printf("%d\n",dt[i]);
}
// void Zengliang(SqList &L, int dt[]) {
// for (int i = 1; i <=L.length; ++i) {
// dt[i-1] = pow(2, i) - 1;
// }
// }
void InPut(SqList &L) {
int i;
srand((unsigned)time(NULL));
cin >> L.length;
for (i = ; i <= L.length; ++i) {
// cin >> L.r[i].key;
L.r[i].key = Random(, );
}
}
void OutPut(SqList &L) {
int i;
for (i = ; i <= L.length; ++i) {
cout << L.r[i].key << " ";
}
}
// void test (SqList &L, int dt[]) {
// int i;
// for (i = 0; i < L.length; ++i)
// printf("%d\n",dt[i]);
// }
int main() {
int dt[] = {, , };
SqList L;
// L.r = new RedType [MAXSIZE+1];
InPut(L);
// Zengliang(L, dt);
// test(L, dt);
ShellSort(L, dt, );
OutPut(L);
return ;
}