文档介绍：选第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>6,∴不能直接找,进入(2);(2)按5个一组分组:(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)。选第k小元素(2)按5个一组分组:(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)。(3)每组按升序排序:(8,17,33,51,57);(11,25,35,37,49);(2,3,13,14,52);(6,12,29,32,54);(5,7