实验二查找k1k2问题实验报告

1、精选优质文档-倾情为你奉上实验二：用分治法查找k1-k2问题实验内容从包含n个整数的无序列表中输出第k1小到第k2小之间的所有整数，其中k1<=k2。分析时间复杂度。必须用分治法求解，但是不能简单地重复使用求第k小元素的分治法。禁止使用排序算法求解给出复杂度分析过程 算法思想在解决实验的过程中参考了快速排序中双向扫描的思想。快速排序是一种基于分治技术的重要排序算法。首先选择一个元素，接下来根据该元素的值来划分数组。中轴之前的是小于中轴的数，之后的为大于中轴的数。在这个问题中我们只需要在找到中轴位K1和K2时跳出快排，输出第K1到K2的元素，便得问题的解。在寻找中轴的过程中如果遇到k2则不

2、需要二次快排，否则再次查找中轴为k2。数据结构：顺序表算法1Quicksort(Sqlist &L,int low,int high,int k1,int k2,int &temp) /用Quicksort对子数组排序/快排到中轴为k1返回/输出：k1将数组分为k1前和k1后两部分if(low<high)/长度大于1s=Partition(L,low,high);/分区过程if(s>k1)/如果k1小于中轴，对low到s-1部分快排if(s=k2)temp=1;/中轴为k2记录temp为真Quicksort(L,low,s-1,k1,k2,temp);else if

3、(s<k1)/如果k1大于中轴，对s到high部分快排Quicksort(L,s+1,high,k1,k2,temp);else if(s=k1)/如果k1等于于中轴跳出递归将数组分为大于k1和小于k2两部分return ;Partition(Sqlist &L,int low,int high)/以L.elem0为限位器，以第一个元素为中轴， /输入：顺序表的子顺序表L.elemlow-high/输出：顺序表的一个分区，分裂点的位置作为函数的返回值while(low<high) while(low<high && L.elemhigh>=piv

4、otkey)/ 从表的两端交替地向中间扫描-high;L.elemlow=L.elemhigh;/将比中轴小的记录交替到低端while(low<high && L.elemlow<=pivotkey)+low;L.elemhigh=L.elemlow;/将比中轴大的记录交替到高端L.elemlow=L.elem0;/中轴记录到位return low; 实验过程1、 源程序/*/*从包含n个整数的无序列表中输出第K1小道第k2小之间的所有整数，其中*/*k1<=k2,分析时间复杂度，在这里采用快排的思想分别找出中轴为k1 和k2*/*时输出k1和k2之间的数，便

5、为所需*/*88#include<iostream>using namespace std;/*结构体*struct Sqlist int *elem;/元素指针int length;/长度int listsize;/;/*构造一个空的线性顺序表*void InitList_Sq(Sqlist &L)L.elem=(int *)malloc(100*sizeof(int);/开辟空间L.length=0;L.listsize=100;/初始化/*快排的分区过程*int Partition(Sqlist &L,int low,int high)int pivotkey

6、;L.elem0=L.elemlow;/以L.elem0为限位器pivotkey=L.elemlow;/以第一个元素为中轴while(low<high)/从表的两端交替地向中间扫描while(low<high && L.elemhigh>=pivotkey)-high;L.elemlow=L.elemhigh;/将比中轴小的记录交替到低端while(low<high && L.elemlow<=pivotkey)+low;L.elemhigh=L.elemlow;/将比中轴大的记录交替到高端L.elemlow=L.elem0;/中轴

7、记录到位return low;/返回中轴位置/*用递归选择中轴，根据中轴调用函数int Partition(Sqlist &L,int low,int high)分区，/当中轴为K1时跳出递归*void Quicksort(Sqlist &L,int low,int high,int k1,int k2,int &temp)int s;if(low<high)/长度大于1s=Partition(L,low,high);/分区过程if(s>k1)/如果k1小于中轴，对low到s-1部分快排if(s=k2)temp=1;Quicksort(L,low,s-1,k

8、1,k2,temp);else if(s<k1)/如果k1大于中轴，对s到high部分快排Quicksort(L,s+1,high,k1,k2,temp);else if(s=k1)/如果k1等于于中轴跳出递归将数组分为大于k1和小于k2两部分return ;/*打印第k1小到k2小的元素*void Print(Sqlist L,int k1,int k2)for(int i=k1;i<=k2;i+)cout<<L.elemi<<" "cout<<endl;/*主函数*int main()int n,k1,k2,temp=0;

9、Sqlist List;InitList_Sq(List);/初始化顺序表cout<<"请输入无序数列中整数的个数："<<endl;/用户输入整数个数cin>>n;cout<<"请以空格键隔开输入无序数列："<<endl;/用户输入无序列表for(int i=1;i<=n;i+)cin>>List.elemi;cout<<"您输入的无序数列为："<<endl;Print(List,1,n);/打印序列cout<<"

10、;请输入输出整数的范围：（如第4小到的8小：4 8 ）"<<endl;/用户输入k1和k2的值cin>>k1>>k2;Quicksort(List,1,n,k1,k2,temp);/*一次快排cout<<"当找到中轴为k1后整数的排列情况"<<endl;Print(List,1,n);/*一次快排后数组情况if(temp)/在找到中轴为k1前已经遇到k2为中轴cout<<"在找到中轴为k1前已经遇到k2为中轴，所以第K1小到第k2小之间的所有整数为："<<end

11、l;Print(List,k1,k2);else/在遇到k1之前并未遇到k2所以再次快排分区Quicksort(List,k1,n,k2,k1,temp);/*二次快排cout<<"在找到中轴为k1前未遇到k2为中轴，通过找k2为中轴后整数的排列情况为："<<endl;Print(List,1,n);cout<<"第K1小到第k2小之间的所有整数为："<<endl;Print(List,k1,k2);return 0;实验结论1、 运行截图快排是极不稳定的一种算法,而这个算法是快排的节俭化比不需要完全完成快排，只需要遇到k1和k2为中轴程序便可停止，用键值的比较次数来代表这个算法的效率：1、 用n来表示输入规模2、 基本操作为两个数得比较3