#include<iostream.h>
#include<stdlib.h>
#include<time.h>
const int n=100000;
const int MAXINT=2147483647;

typedef struct{  
int key;       //r[n+1];
int next;
}SLNode;
typedef struct
{
	SLNode *r;
	int length;
}SLinkList;

int random();
void LInsertionSort (SLinkList &SL, int m);
void Arrange(SLinkList &SL);
void main(){  
	
  	SLinkList L;
	L.r = new SLNode[n+1];
	L.length=n;
	for(int i=1;i<=n;i++)
		L.r[i].key=random();
	long t1,t2;	
	t1=clock();
	LInsertionSort(L,n);
   	Arrange(L);
	t2=clock();
	cout<<" 時間: "<<float(t2-t1)/CLK_TCK<<endl;
	
	
}
int random(){
    	int A=48271;
	int M=2147483647;
	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 LInsertionSort (SLinkList &SL, int m) 
  {
      // 對記錄序列SL[1..n]作表插入排序。 
	  int i,j,k;
      SL.r[0].key = MAXINT ; 
      SL.r[0].next = 1;  SL.r[1].next = 0; 
      for ( i=2; i<=m; ++i ) 
       {   
		  for ( j=0, k = SL.r[0].next; SL.r[k].key <= SL.r[i].key ; j = k, k = SL.r[k].next ); 
           SL.r[j].next = i;  SL.r[i].next = k; 
		} 
		
      // 結點i插入在結點j和結點k之間 
  }// LinsertionSort 


void Arrange(SLinkList &SL){
                                                //根據靜態鏈表SL中各結點的指針值調整記錄位置,使得SL中記錄按關鍵字非遞減有序順序排列
int p,q,i;
SLNode temp;
p=SL.r[0].next;                                 //p指示第一個記錄的當前位置
for(i=1;i<SL.length;++i){                        //SL.r[1..i-1]中記錄已按關鍵字有序排列,第
                                               //個記錄在SL中的當前位置應不小于i
while(p<i) p=SL.r[p].next;                     //找到第i個記錄,并用p指示其在SL中的
                                               //當前位置
q=SL.r[p].next;                                //q指示尚未調整的表尾
if(p!=i){
temp=SL.r[p]; SL.r[p]= SL.r[i]; SL.r[i]=temp;  //交換記錄,使第i個記錄到位
SL.r[i].next=p;                                //指向被移走的記錄,使得以后可由while循環找回
}
p=q;                                           //q指示尚未調整的表尾,為找第i+1個記錄作準備
}
}