大二算法设计实验源码

#include<iostream>
#include<stdlib.h>
#include<iomanip>
using namespace std;

int Select(int a[],int,int,int);
void Quicksort(int a[],int,int);
int Partition(int a[],int,int,int);
void Swap(int &,int &);

void main(){
	int m,n;
	cout<<"请输入要产生的随机数的个数：";
	cin>>m;
	int *a=new int[m];
	for(int i=0;i<m;i++)
		a[i]=rand()%100;
	for(i=0;i<m;i++)
		cout<<setw(4)<<a[i];
	cout<<"要找第几小的元素？";
	cin>>n;
	cout<<"结果是："<<Select(a,0,m-1,n)<<endl;
}

int Select(int a[],int p,int r,int k){
	if(r-p+1<75){
		Quicksort(a,p,r);
		return a[p+k-1];
	}
	for(int i=0;i<(r-p+1)/5;i++){
		Quicksort(a,(p+5*i),(p+5*i+4));
		Swap(a[i],a[5*i+2]);
	}
	int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
	i=Partition(a,p,r,x);
	int j=i-p+1;
	if(k<=j) return Select(a,p,i,k);
	else return Select(a,i+1,r,k-j);
}

void Quicksort(int a[],int p,int r){
	if(p<r){
		int q=Partition(a,p,r,a[0]);
		Quicksort(a,p,q-1);
		Quicksort(a,q+1,r);
	}
}

int Partition(int a[],int p,int r,int x){
	int i=p,j=r+1;
	while(1){
		while(a[++i]<x&&i<r);
		while(a[--j]>x);
		if(i>=j) break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

void Swap(int &a,int &b){
	int x;
	x=a;
	a=b;
	b=x;
}