选择算法举例【动态演示】

1、选第k小元素选第k小元素问题描述：在n个元素的无序数组中选择第k(1=k=n)小元素。当k=1时，相当于找最小值。当k=n时，相当于找最大值。当k=n/2时，称中值。基于划分的选择算法A128=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,93,7,5,6,2,8,11,25,37,14,35,49

2、,13,52,12,57,29,32,54,51,16,22,23,17,61,36,33,9jk，在右边区间找第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,25jk，在左边区间找第k(=6)小元素j=14线性时间选择算法算法：元素的个数大于阈值（可取为6）时往下，否则直接计算；把元素按5个一组，分为 组；5n若不是5的倍数，剩下元素不做处理，不影响算法性能；将每组排序，其第3个元素恰好是中值；递归地计算这些中值，把这些中值的中值用m表示；把数组元素分为三组：A1、A2和A3，它们分别是包

3、含小于、等于和大于m的元素；确定第k小元素的出现则返回，或在A1和A3中递归调用。选第k小元素例：取阈值为6，设数组A有28个元素如下，A128=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)(1) 286，不能直接找，进入(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

4、,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,16,22,23)。(4)中值的集合M=33,35,13,29,16。(5)递归找到中值的中值m=29。选第k小元素(5)递归找到中值的中值m=29。(6)把A分为三组：A1= 8,17,11,25,14,3,2,13,12,6,5,16,22,23,7,9;A2=29;A3=33,51,57,49,35,37,52,32,54,61,36。因为k=14|A1|+|A2|=11，丢掉A1和A2，而第14小元素必然在A3中。选第k小元素(13)设A=A3=17,25,16,22,23然后在A3中找第k(=14-11