快速排序.cpp

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

#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