实验二减治法查找范围整数
学院：计算机科学与技术专业：计算机科学与技术
学号：班级：姓名：
一、实验内容：
从包含n个整数的无序列表中输出第k1小到第k2小之间的所有整数，其中k1<=k2。

分析时间复杂度。

二、算法思想：
减治法的基本思想：规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：
（1）原问题的解只存在于其中一个较小规模的子问题中；
（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。

由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。

一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。

减治法查找范围整数的思想：先把输入的无序列表中的每个整数都标记为1，用f1和f2存储每次查找的最大和最小的整数，并标记为0，作为删除。

接着循环递归，直到将范围缩小到k1->k2.时就得到了所要的结果。

三、实验过程：
#include<iostream>
using namespace std;
#define max 100
typedef struct Data
{
int data;
bool flag;
}Data,Mat[max];
Mat a;
void Found_k1_k2(Mat &a,int n,int k1,int k2)//用减治法查找无序列表中第k1到第k2小的整数
{
int x=0;
int y=n-1;
while(x<k1-1||y>k2-1)
{
int temp;
int f1,f2;//存储最小和最大数的下标
f1=x;
f2=y;
for(int i=x; i<=y; i++)
{
if(a[f1].data>a[i].data)
f1=i;
if(a[f2].data<a[i].data)
f2=i;
}
if(x<k1-1)
{
temp=a[x].data;
a[x].data=a[f1].data;
a[f1].data=temp;
a[x].flag=0;
x++;
}
if(y>k2-1)
{
temp=a[y].data;
a[y].data=a[f2].data;
a[f2].data=temp;
a[y].flag=0;
y--;
}
}
}
void Show(Mat &a,int n,int k1,int k2)
{
cout<<"第"<<k1<<"小到"<<k2<<"小之间的所有整数有:";
for(int i=0; i<n; i++)
{
if(a[i].flag)
cout<<a[i].data<<" ";
}
cout<<endl;
}
void main()
{
int choice;
cout<<" 1: 执行程序！2: 退出程序！"<<endl;
do
{
cout<<"请选择你的操作:";
cin>>choice;
switch(choice)
{
case 1:
{
int n;
int k1,k2;
cout<<"请输入无序列表n的大小:";
cin>>n;
cout<<"请输入无序列表中的所有整数:";
for(int i=0; i<n; i++)
{
a[i].flag=1;
cin>>a[i].data;
}
cout<<"请输入k1，k2的值:";
cin>>k1>>k2;
if(k1>k2)
{
int temp=k1;
k1=k2;
k2=temp;
}
if(k1<0||k2>n||n<0)
{
cout<<"输入不和法!!请重新输入!!"<<endl;
break;
}
Found_k1_k2(a,n,k1,k2);
Show(a,n,k1,k2);
break;
}
case 2:
{
cout<<"退出程序！";
break;
}
default:cout<<"选择不合理，请重选！"<<endl;
}
}
while(choice!=2);
}
四、实验结果：
该算法的时间复杂度取决于n的大小和输入的K1、K2的情况，最好情况是K1、K2恰好在输入的无序列表的两端，此时不做运算，直接输出，时间复杂度为O(0)。

最坏情况是K1=K2=n/2时，此时做n/2次运算，时间复杂度为O(n/2)。