改进2表插入排序.cpp

八种排序的方法,利用VC++实现,值得借鉴

#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个记录作准备
}
}