实验二：查找k1-k2问题实验报告-2

实验二：用分治法查找k1-k2问题实验内容从包含n个整数的无序列表中输出第k1小到第k2小之间的所有整数，其中k1=k2。分析时间复杂度。必须用分治法求解，但是不能简单地重复使用求第k小元素的分治法。禁止使用排序算法求解给出复杂度分析过程算法思想在解决实验的过程中参考了快速排序中双向扫描的思想。快速排序是一种基于分治技术的重要排序算法。首先选择一个元素，接下来根据该元素的值来划分数组。中轴之前的是小于中轴的数，之后的为大于中轴的数。在这个问题中我们只需要在找到中轴位K1和K2时跳出快排，输出第K1到K2的元素，便得问题的解。在寻找中轴的过程中如果遇到k2则不需要二次快排，否则再次查找中轴为k2。数据结构：顺序表算法1Quicksort(Sqlist&L,intlow,inthigh,intk1,intk2,int&temp)//用Quicksort对子数组排序//快排到中轴为k1返回//输出：k1将数组分为k1前和k1后两部分if(lowhigh)//长度大于1{s=Partition(L,low,high);//分区过程if(sk1)//如果k1小于中轴，对low到s-1部分快排{if(s==k2)temp=1;//中轴为k2记录temp为真Quicksort(L,low,s-1,k1,k2,temp);}elseif(sk1)//如果k1大于中轴，对s到high部分快排{Quicksort(L,s+1,high,k1,k2,temp);}elseif(s=k1)//如果k1等于于中轴跳出递归将数组分为大于k1和小于k2两部分{return;}Partition(Sqlist&L,intlow,inthigh)//以L.elem[0]为限位器，以第一个元素为中轴，//输入：顺序表的子顺序表L.elem[low-high]//输出：顺序表的一个分区，分裂点的位置作为函数的返回值while(lowhigh){while(lowhigh&&L.elem[high]=pivotkey)//从表的两端交替地向中间扫描--high;L.elem[low]=L.elem[high];//将比中轴小的记录交替到低端while(lowhigh&&L.elem[low]=pivotkey)++low;L.elem[high]=L.elem[low];//将比中轴大的记录交替到高端}L.elem[low]=L.elem[0];//中轴记录到位returnlow;实验过程1、源程序//****************************************************************************//****从包含n个整数的无序列表中输出第K1小道第k2小之间的所有整数，其中********//********k1=k2,分析时间复杂度，在这里采用快排的思想分别找出中轴为k1和k2***//*********时输出k1和k2之间的数，便为所需*************************************//***************************************************************************88#includeiostreamusingnamespacestd;//***************结构体**********structSqlist{int*elem;//元素指针intlength;//长度intlistsize;//};//************构造一个空的线性顺序表************voidInitList_Sq(Sqlist&L){L.elem=(int*)malloc(100*sizeof(int));//开辟空间L.length=0;L.listsize=100;//初始化}//***********快排的分区过程******************intPartition(Sqlist&L,intlow,inthigh){intpivotkey;L.elem[0]=L.elem[low];//以L.elem[0]为限位器pivotkey=L.elem[low];//以第一个元素为中轴while(lowhigh)//从表的两端交替地向中间扫描{while(lowhigh&&L.elem[high]=pivotkey)--high;L.elem[low]=L.elem[high];//将比中轴小的记录交替到低端while(lowhigh&&L.elem[low]=pivotkey)++low;L.elem[high]=L.elem[low];//将比中轴大的记录交替到高端}L.elem[low]=L.elem[0];//中轴记录到位returnlow;//返回中轴位置}//**********用递归选择中轴，根据中轴调用函数intPartition(Sqlist&L,intlow,inthigh)分区，//当中轴为K1时跳出递归*****************************************************voidQuicksort(Sqlist&L,intlow,inthigh,intk1,intk2,int&temp){ints;if(lowhigh)//长度大于1{s=Partition(L,low,high);//分区过程if(sk1)//如果k1小于中轴，对low到s-1部分快排{if(s==k2)temp=1;Quicksort(L,low,s-1,k1,k2,temp);}elseif(sk1)//如果k1大于中轴，对s到high部分快排{Quicksort(L,s+1,high,k1,k2,temp);}elseif(s=k1)//如果k1等于于中轴跳出递归将数组分为大于k1和小于k2两部分{return;}}}//************打印第k1小到k2小的元素******************voidPrint(SqlistL,intk1,intk2){for(inti=k1;i=k2;i++)coutL.elem[i];coutendl;}//**********主函数********************intmain(){intn,k1,k2,temp=0;SqlistList;InitList_Sq(List);//初始化顺序表cout请输入无序数列中整数的个数：endl;//用户输入整数个数cinn;cout请以空格键隔开输入无序数列：endl;//用户输入无序列表for(inti=1;i=n;i++)cinList.elem[i];cout您输入的无序数列为：endl;Print(List,1,n);//打印序列cout请输入输出整数的范围：（如第4小到的8小：48）endl;//用户输入k1和k2的值cink1k2;Quicksort(List,1,n,k1,k2,temp);//**************一次快排cout当找到中轴为k1后整数的排列情况endl;Print(List,1,n);//*************************************一次快排后数组情况if(temp)//在找到中轴为k1前已经遇到k2为中轴{cout在找到中轴为k1前已经遇到k2为中轴，所以第K1小到第k2小之间的所有整数为：endl;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);}return0;}实验结论1、运行截图快排是极不稳定的一种算法,而这个算法是快排的节俭化比不需要完全完成快排，只需要遇到k1和k2为中轴程序便可停止，用键值的比较次数来代表这个算法的效率：1、用n来表示输入规模2、基本操作为两个数得比较3、4、和5、当n1时，最差：C（n）=C(n-1)+n=n*n,C(1)=0最好：只需要一次的对半排列C（n）=C(n/2)+n,C(1)=0,当n等于2的次幂时C（n）=nlog2(n)假设分区的分裂点s(0s=n)位于每个位置的概率都是1/n,平均：C（n）=1/2n∑(n+C(s)+C(n-1-s))=vlNn