河北地质大学
课程设计报告
(学 院)系: 信息工程学院 专 业: 计算机科学与技术 姓 名: 李义 班 级: 二班 学 号: 515109030227 指导教师: 王培崇
2016年 11月 26 日
算法课程设计报告 姓名 实验室 设计题目 李义 152 学号 515109030227 指导教师 日期 王培崇 2016/11/10-2016/12/1 设备编号 08 寻找第k小元素 一、设计内容 在数组中找到第k小，即在此数组中 1,22,33,522,11,7,3,6,10,5,3,21,2,1,56,5,67,44,32此时输入k=6，找到的值为5 二、设计目的 加深对分治思想的理解。 三、设计过程 1. 算法设计 1. select(A,1,n,k) 过程select(A,low,high,k) 1. p high-low+1 2. if p<6 then 将A排序return(A[k]) 3. 令q= p/5。将A分成q组，每组5个元素。如果5不整除p，则排除剩余的元素。 4. 将q组中的每一组单独排序，找出中项。所有中项的集合为M。 5. mmselect(M,1,q, q/2 ) {mm为中项集合的中项} 6. 将A[low…high]分成三组 A1={a|amm} 7. case |A1|≥k:return select(A,1,|A1|,k) |A1|+|A2| ≥k:return mm |A1|+|A2|
