/*2、线性时间选择(分治策略)
实验数据:实验测试数据(100个).dat(共100个数据)
——要求找出序列中最小的元素*/
#include <iostream>
#include<fstream>
using namespace std;
const char *infile="input.dat"; //输入文件路径
const int N=100; //input.dat中有100个数据
void swap(int *a, int *b){
int tmp=*a;
*a=*b;
*b=tmp;
}
void bubbleSort(int *a,int first,int end) //冒泡排序
{
for(int i = first; i < end; i++)
for(int j = end; j > i; j--)
if(a[j]<a[j-1])
{
swap(&a[j], &a[j - 1]);
}
}
//数组a中从a[p]到a[r]的元素按照x划分,大于x的在左边,小于x的在右边
int partition(int *a,int p, int r, int x){
int i=p-1,j=r+1;
while(true){
while(a[++i]<x&&i<r);
while(a[--j]>x&&j>p);
if(i>=j)
break;
swap(&a[i],&a[j]);
}
return j;
}
//选择数组中第k小的元素
int select(int *a,int p,int r,int k)
{
if(r-p<75)
{
bubbleSort(a,p,r);
return a[p+k-1];
}
for(int i=0;i<=(r-p-4)/5;i++)
{
int s=p+5*i;
int t=s+4;
for(int j=0;j<3;j++)
bubbleSort(a,s,t-j);
swap(&a[p+i],&a[s+2]);
}
int x=select(a,p,p+(r-p-4)/5,(r-p+6)/10); //x为中位数的中位数
int o=partition(a,p,r,x);
int j=o-p+1;
if(k<=j) return select(a,p,o,k);
else return select(a,o+1,r,k-j);
}
int main()
{
int data; //保存文件中读出的临时数据
int a[100]; //数组a存放文件中的100个数据
int s=0; //数组的下标
int min; //获得的最小的元素
ifstream fin;
fin.open(infile);
cout<<"文件中的100个数据为:"<<"\n";
if(fin.is_open())
{
while(fin>>data)
{
cout<<data<<"\t";
a[s++]=data;
}
}
else cerr<<"Open error";
min=select(a,0,N-1,1);
cout<<"\n"<<"最小的元素是:"<<min<<endl;
fin.close();
return 0;
}