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

const int n=1000000;

typedef struct{
	int key;
}RedType;

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



int random();
int partition(SqList &L,int low,int high);
void QSort(SqList &L,int low,int high);
void main()
{ 
	
    int t,m;
  	SqList L;
	L.r = new RedType[n+1];
	L.length=n;
	for(int i=1;i<=n;i++)	L.r[i].key=random();//O(n)
	long t1,t2;	
	t=1;
	m=n;
	t1=clock();
	QSort(L,t,m);
	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;
}


int partition(SqList &L,int low,int high)
{
	int pivotkey;
	//交換順序表L中子表r[low..high]的記錄,樞軸記錄到位,并返回其所在位置,此時在它之前(后)的//記錄均不大(小)于它.
	L.r[0]=L.r[low];                       //用子表的第一個記錄作樞軸記錄
	pivotkey=L.r[low].key;                 //樞軸記錄關鍵字
	while(low<high)
	{//從表的兩端交替的向中間掃描
		while(low<high&&L.r[high].key>=pivotkey) --high;
		L.r[low]=L.r[high];             //將樞軸記錄小的記錄移到低端
		while(low<high&&L.r[low].key<=pivotkey) ++low;
		L.r[high]=L.r[low];             //將樞軸記錄大的記錄移到高端
	}
	L.r[low]=L.r[0];                      //樞軸記錄到位
	return low;                          //返回樞軸位置
}// partition

void QSort(SqList &L,int low,int high)
{
	int pivotloc;
	//對順序表L中的子序列L.r[low..high]做快速排序
	if (low<high){                      //長度大于1
	pivotloc=partition(L,low,high);       //將L.r[low..high]一分為二
	QSort(L,low,pivotloc-1);            //對低子表遞歸排序,pivotloc是樞軸位置
	QSort(L,pivotloc+1,high);          //對高子表遞歸排序
	}
}//QSort