qsort.cpp

快速排序算法是基于分治策略的另一个排序算法。其基本思想是

#include"iostream.h"

static unsigned int RAND_SEED=1;
unsigned int random(void)//产生随机数
{
    RAND_SEED=(RAND_SEED*123+59)%65536;
    return(RAND_SEED);
}
void random_start(int xxx)//初始种子
{
	RAND_SEED=xxx;
}

int *onerange(int   n)   //产生随机序列
{   
	int i;
	int   *d   =   new   int[n];  
	int  *range=new int[n];
	int seed=0;
	unsigned   int   a;   
	for   (i=0;   i<n;   i++)   
	{   
		*(d+i)   =   i+1;   
	}   
	for   (i=0;   i<n;)   
	{  
		random_start(seed);
		a=random(); 
		seed=a;
		a   %=   n;   
		if   (*(d+a)!=-1)   
		{
			range[i]=*(d+a);//cout<<*(d+a)<<"\t";   
			*(d+a)   =   -1;   
			i++;   
		}   
	} 
	delete d;
	return range;
}


void qSort(int a[], int n, int p, int r){
	if(p < r){
		int i=p;
		int j=r+1;
		int x=a[p];//以a[p]为基准元素将数组划分为两段
		int tmp;
		while(true){
			while(a[++i] < x);
			while(a[--j] > x);
			if(i>=j)
				break;
			tmp=a[i];
			a[i] = a[j];
			a[j] = tmp;
		}
		a[p] = a[j];
		a[j] = x;

		qSort(a, n, p, j-1);//对左半段排序
		qSort(a, n, j+1, r);//对右半段排序
	}
}
void main()
{
	int n=50;
	int *p=onerange(n);
	qSort(p,n,0,n-1);
	for(int i=0;i<n;i++)
		cout<<p[i]<<endl;
	delete []p;
}