实验程序.txt

快速排序采用随机数产生种子 程序中的快速排序采用随机数来产生种子 提高了算法的效率 同时在概率算法中也有很好的实用性

#include<iostream>
#include<ctime>
#include<cmath>
using namespace std;
//随机数产生函数
int Random(int n)
{
	int *a=new int[n],j=0;
	srand((unsigned)time(NULL)); 
	for(int i=0;i<n;i++) 
	{
		a[i]=rand()%10; 
	}
	for(i=0;i<n;i++)
	{
	  if(a[i]<n)i++;
	  else j=a[i];
	}
	
	cout<<"产生的随机数是"<<j<<endl;
    return j;
}
// 交换两个数的数值
void Swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}
int Partition(int a[],int p,int r)
{
	int i=p,j=r+1;
	int x=a[p];
	//将 <x 的元素放到左边
	//将 >x 的元素放到右边
	while(!0)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j)break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
int RandomizedPartition(int a[],int p,int r)
{
	int j=r-p;
	int b=Random(j);
	int i=j+p;
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
void RandomizedQuickSort(int a[],int p,int r)
{
	if(p<r)
	{
		int q=RandomizedPartition(a,p,r);
		//对左半段排序
		RandomizedQuickSort(a,p,q-1);
		//对右半段排序
		RandomizedQuickSort(a,q+1,r);
	}
}

void main()
{
	int n=0, i,j;
	cout<<"请输入数组元素的个数："<<endl;
	cin>>n;
	int *A=new int[n];
	cout<<"请输入"<<n<<"个数组元素："<<endl;
	for(i=0;i<n;i++)
		cin>>A[i];
	RandomizedQuickSort(A,0,n-1);
	cout<<"合并排序后得到的数组为:"<<endl;
	for(j=0;j<n;j++)
		cout<<A[j]<<endl;
}