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

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


int random();
void SelectSort(SLinkList &SL ,int m);
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();
   	SelectSort(L,n);
	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 SelectSort(SLinkList &SL ,int m){                    //直接選擇排序
int i,j,k;
for(i=1;i<=m-1;i++){                               //n-1趟排序
k=i;
for(j=i+1;j<=m;j++)                               //在當前無序區中找鍵值最小的記錄R[k]
if ( SL.r[j].key<SL.r[k].key ) k=j;
if (k!=i) { SL.r[0]=SL.r[i];SL.r[i]=SL.r[k];SL.r[k]=SL.r[0]; }            //交換R[i]和R[k],R[0]作輔助量
}
}