1、线性时间选择中位数湖南涉外经济学院 计算机科学与技术专业算法设计与分析课程 线性时间选择(中位数) 实 验 报 告班级: 学号: 姓名: 教师: 成绩: 2012年5月【实验目的】1 掌握线性时间选择的基本算法及其应用2 利用线性时间选择算法找出数组的第k小的数3 分析实验结果,总结算法的时间和空间复杂度【系统环境】Windows7 旗舰版 平台【实验工具】VC+6.0英文企业版【问题描述】 描述: 随机生成一个长度为n的数组。数组为随机生成,k由用户输入。在随机生成的自然数数组元素找出这n个数的第k小的元素。例: A5=3,20,50,10,21 k=3,则在数组A中第3小的元素为20【实验
2、原理】原理:将所有的数(n个),以每5个划分为一组,共n/5组(将不足五个的那组忽略);然后用任意一种排序算法(因为只对五个数进行排序,所以任取一种排序法就可以了,这里我选用冒泡排序),将每组中的元素排好序再分别取每组的中位数,得到n/5个中位数;再取这n/5个中位数的中位数(如果n/5是偶数,就找它的2个中位数中较大的一个)作为划分基准,将全部的数划分为两个部分,小于基准的在左边,大于等于基准的放右边。在这种情况下,找出的基准x至少比3(n-5)/10个元素大,因为在每一组中有2个元素小于本组的中位数,中位数处于1/2*n/5-1,即n/5 个中位数中又有(n-5)/10个小于基准x。同理,
3、基准x也至少比3(n-5)/10个元素小。而当n75时,3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。思路:如果能在线性时间内找到一个划分基准,使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数),那么就可以在最坏情况下用O(n)时间完成选择任务。例如:若=9/10,算法递归调用所产生的子数组的长度至少缩短1/10。所以,在最坏情况下,算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。方法:利用函数的相互调用和函数的递归调用实现程序的最终实现,一个主函数,三个子函数。在主函数中只
4、是单独的调用中位数算法的select函数,然后以select为入口进行调用bubble排序函数和partition划分函数。【源程序代码】#include#include#includeusing namespace std;#define MAX_VALUE 100#define random() rand()%MAX_VALUE#define N 10#define MIDDLE 5int aN;class Findpublic:/冒泡排序void bubble(int first,int end) for(int i = first; i i; j-) if(ajaj-1) swap(a
5、j, aj - 1); /数组a中从ap到ar的元素按照x划分,大于x的在左边,小于x的在右边int partition(int p,int r,int x) int i = p - 1, j = r + 1; while (1) while (a+i x & i x); if (i = j) break; swap(ai, aj); return j - 1; /寻找中位数int select(int p,int r,int k) if(r - p 75) bubble(p,r); return ap+k-1; for(int i = 0; i (r - p - 4) / 5; i+) in
6、t s = p + 5 * i, t = s + 4; bubble(s,t); int temp = ap + i; ap + i = as + 2; as + 2 = temp; / 找中位数的中位数 int x = select(p, p + (r - p - 4) / 5, (r - p - 4) / 10); i = partition(p, r, x); int j = i - p + 1; if(k = j) return select(p, i, k); else return select(i + 1, r, k - j); ;int main() srand(int)time(NULL); for(int k = 0; k N; k+) ak = random(); cout ak t; cout endl; Find f; int n = MIDDLE; cout The No. n is : f.select(0, N-1, n) endl; return 0;【实验结果】 运行结果图(k=5):运行结果图(k=4):实验结果分析:通过上面的结果图可以证明程序可以得到正确的排序结果。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2