選擇算法舉例【動(dòng)態(tài)演示】

1、選第k小元素選第k小元素問題描述：在n個(gè)元素的無序數(shù)組中選擇第k(1=k=n)小元素。當(dāng)k=1時(shí)，相當(dāng)于找最小值。當(dāng)k=n時(shí)，相當(dāng)于找最大值。當(dāng)k=n/2時(shí)，稱中值?；趧澐值倪x擇算法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，在右邊區(qū)間找第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，在左邊區(qū)間找第k(=6)小元素j=14線性時(shí)間選擇算法算法：元素的個(gè)數(shù)大于閾值（可取為6）時(shí)往下，否則直接計(jì)算；把元素按5個(gè)一組，分為 組；5n若不是5的倍數(shù)，剩下元素不做處理，不影響算法性能；將每組排序，其第3個(gè)元素恰好是中值；遞歸地計(jì)算這些中值，把這些中值的中值用m表示；把數(shù)組元素分為三組：A1、A2和A3，它們分別是包

3、含小于、等于和大于m的元素；確定第k小元素的出現(xiàn)則返回，或在A1和A3中遞歸調(diào)用。選第k小元素例：取閾值為6，設(shè)數(shù)組A有28個(gè)元素如下，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，不能直接找，進(jìn)入(2)；(2)按5個(gè)一組分組：(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個(gè)一組分組：(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。因?yàn)閗=14|A1|+|A2|=11，丟掉A1和A2，而第14小元素必然在A3中。選第k小元素(13)設(shè)A=A3=17,25,16,22,23然后在A3中找第k(=14-11