#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<stdio.h>

const int n=10000000;

typedef struct{
	int key;
}RedType;

typedef struct{  
RedType  *r;       //r[n+1];
int length;
}SqList;



int random();
void ShellInsert(SqList &SL,int h);
void ShellSort(SqList &SL,int t);
void main(){ 
	int t;
  	SqList L;
	L.r = new RedType[n+1];
	L.length=n;
	for(int i=1;i<=n;i++)	L.r[i].key=random();
	long t1,t2;	
	t1=clock();
   	ShellInsert(L,n);
	t=log10(double(n+1))/log10(double(2));
	ShellSort(L,t);
	t2=clock();
	cout<<" 時間: "<<float(t2-t1)/CLK_TCK<<endl;
	
	
}
int random(){
    	int A=48271;
	int M=2147483646;
	int Q=M/A;
	int R=M%A;
	static int x=1;	int x1;
	x1=A*(x%Q)-R*(x/Q);
	if(x1>=0) x=x1;
	else	x=x1+M;
	return x;
}


void ShellInsert(SqList &SL,int h){    //對順序表L作一趟希爾排序.本算法是和一趟直接插入排序相比,作了以下修改:
									//1.前后記錄位置的增量是h,而不是1;
									//2.r[0]只是暫存單元,不是哨兵.當(dāng)j<=0時,插入位置已找到.
int i,j;
for(i=h+1;i<=SL.length;i++)               //i為組號
if(SL.r[i].key>=SL.r[i-h].key) {   //R[j]大于有序區(qū)最后一個記錄,則不需要插入
SL.r[0]=SL.r[i];                      //R[0]保存待插記錄,但不是監(jiān)視哨
for(j=i-h;j>0&&(SL.r[0].key>=SL.r[j].key);j-=h )
SL.r[j+h]=SL.r[j];
SL.r[j+h]=SL.r[0];
}
}


void ShellSort(SqList &SL,int t){     //d[]為增量序列,t為增量序列長度
int i,dlta;
for(i=0;i<t;i++) 
{                       //各趟插入排序
	dlta=pow(2,t-i+1)-1;
    ShellInsert(SL,dlta);
	if(dlta==1)
		break;
}
}