求第k小元素：采用特定分治策略

1. 问题

设L是n个元素的集合，从L中选取第k小的元素，其中1<=k<=n.这里的第k小元素是指，当L按从小到大排好序之后，排在第k个位置的元素。

对于这个算法而言，最关键的是需要找出m*这个数字，相较于一般分治策略而言，m*能够最大限度地避免最坏的情况出现。

备注：S1为小于*m的元素的集合，S2为大于*m的元素的集合，

有如下几个步骤：

① 将L中的元素分为组，每组有5个元素，并将每组5个元素排序并找出每组的中位数（如图红、黑点）

② 找出所有组中位数的中位数，将该数定义为m*（如图红点），此时可将所有元素分为A、B、C、D四个区域，根据之前的处理可知，C区域的元素均小于m*，可划入S1集合；C区域的元素均大于m*，可划入S2集合

③ 接下来处理A、D两块区域，分别遍历这两块区域，将小于m*的元素划入S1集合，大于m*的元素可划入S2集合

④ 判断|S1|的大小和k的关系，若|S1|+1=k,则表明m*为所要查询的元素；|S1|<k，则递归进入S2中寻找第k-|S1|-1大的元素；|S1|>k,则递归进入S1寻找第k大的元素。