线性时间选择中位数

《线性时间选择中位数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖南涉外经济学院计算机科学与技术专业《算法设计与分析》课程线性时间选择（中位数）实验报告班级：学号：姓名：教师：成绩：2012年5月【实验目的】1掌握线性时间选择的基本算法及其应用2利用线性时间选择算法找出数组的第k小的数3分析实验结果，总结算法的时间和空间复杂度【系统环境】Windows7旗舰版平台【实验工具】VC++6.0英文企业版【问题描述】描述：随机生成一个长度为n的数组。数组为随机生成，k由用户输入。在随机生成的自然数数组元素找出这n个数的第k小的元素。例：A[5]={3,20,50,10,21}k=3,则在数组A中第3小的

2、元素为20【实验原理】原理：将所有的数（n个），以每5个划分为一组，共[n/5]组（将不足五个的那组忽略）；然后用任意一种排序算法（因为只对五个数进行排序，所以任取一种排序法就可以了，这里我选用冒泡排序），将每组中的元素排好序再分别取每组的中位数，得到[n/5]个中位数；再取这[n/5]个中位数的中位数（如果n/5是偶数，就找它的2个中位数中较大的一个）作为划分基准，将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，中

3、位数处于1/2*[n/5-1]，即n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。思路：如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如：若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归

4、式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。方法：利用函数的相互调用和函数的递归调用实现程序的最终实现，一个主函数，三个子函数。在主函数中只是单独的调用中位数算法的select函数，然后以select为入口进行调用bubble排序函数和partition划分函数。【源程序代码】#include#include#includeusingnamespacestd;#defineMAX_VALUE100#definerandom()rand()%MAX_VALU

5、E#defineN10#defineMIDDLE5inta[N];classFind{public://冒泡排序voidbubble(intfirst,intend){for(inti=first;ii;j--)if(a[j]

6、]x);if(i>=j)break;swap(a[i],a[j]);}returnj-1;}//寻找中位数intselect(intp,intr,intk){if(r-p<75){bubble(p,r);returna[p+k-1];}for(inti=0;i<(r-p-4)/5;i++){ints=p+5*i,t=s+4;bubble(s,t);inttemp=a[p+i];a[p+i]=a[s+2];a[s+2]=temp;}//找中位数的中位数intx=select(p,p+(r-p-

7、4)/5,(r-p-4)/10);i=partition(p,r,x);intj=i-p+1;if(k<=j)returnselect(p,i,k);elsereturnselect(i+1,r,k-j);}};intmain(){srand((int)time(NULL));for(intk=0;k

8、return0;}【实验结果】运行结果图（k=5）：运行结果图（k=4）：实验结果分析：通过上面的结果图可以证明程序可以得到正确的排序结果。