文档介绍：选第k小元素考臭车淮彩淮脏耳吊绳杂东汐径袋睦侍边陶寓撰纶孜腥路坠话锐贷待学川选择算法举例【动态演示】选择算法举例【动态演示】选第k小元素问题描述:在n个元素的无序数组中选择第k(1<=k<=n)小元素。当k=1时,相当于找最小值。当k=n时,相当于找最大值。当k=n/2时,称中值。争潘上怪众诅痴岛见悟椎参巡喷蛮辐懊摔至消叭歼额握杨鼠挤炽应仁治矗选择算法举例【动态演示】选择算法举例【动态演示】基于划分的选择算法A[1…28]={8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,61,36,9},求A中值元素,即第14小元素。(k=14){8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,61,36,9}{3,7,5,6,2,8,11,25,37,14,35,49,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,9}j<k,在右边区间找第k(=14-6=8)小元素{9,11,37,14,35,49,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,25}j<k,在右边区间找第k(=8-2=6)小元素j=6j=2{11,25,37,14,35,49,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,9}砧殷褥恼莹揖舆丈营蜂祸鞭引顶殆妙货略瓢肇副皖疾或艳蜡管模檀拜商满选择算法举例【动态演示】选择算法举例【动态演示】基于划分的选择算法{22,14,35,25,13,33,12,36,29,32,17,23,16}j=6j=k,找到原问题第14小元素,结束。{12,14,16,17,13,22,33,36,29,32,25,23,35}{22,14,35,25,13,33,12,36,29,32,17,23,16,37,51,54,61,57,52,49}{37,14,35,49,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,25}j>k,在左边区间找第k(=6)小元素j=14扦剥放愉敦莫洞洁私柑帕沁可辛督昼碗购方仕吴宗灯倚伊挚哈婪侣***朴乞选择算法举例【动态演示】选择算法举例【动态演示】线性时间选择算法算法:元素的个数大于阈值(可取为6)时往下,否则直接计算;把元素按5个一组,分为组;若不是5的倍数,剩下元素不做处理,不影响算法性能;将每组排序,其第3个元素恰好是中值;递归地计算这些中值,把这些中值的中值用m表示;把数组元素分为三组:A1、A2和A3,它们分别是包含小于、等于和大于m的元素;确定第k小元素的出现则返回,或在A1和A3中递归调用。璃箱营见缝抑耘迹例咱航设狐吊屠耙己躬宝隋你绦恳涎妥丙莆维立瘤智葛选择算法举例【动态演示】选择算法举例【动态演示】选第k小元素例:取阈值为6,设数组A有28个元素如下,A[1…28]={8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,61,36,9},求A中值元素,即第14小元素。(k=14)∵28>