K个最大（最小）元素的算法

问题描述：给定具有个元素的全序集合，比较算符为，求最大的个元素，不要求排序。下面按照取K个最小值的情况讨论。
基本思想：类似于快速排序法，选择一个元素将其插入到数组的一个位置，使得左侧的元素都小于等于该标记元素，右侧元素都大于等于该元素。

• 取第一个元素为标记元素，扫描后续的元素，并与其比较，分为三类
  • 一类是全部小于该元素，数组计为，个数计为
  • 一类是全部等于该元素，数组计为，个数计为
  • 一类是全部大于该元素，数组计为，个数计为
  • 定义
• 将与比较，确定其位置。
• 当时，返回结果即
• 当时，返回结果即
• 当时，返回结果即集合本身
• 当时，对集合递归调用上述过程
• 当时，在集合中递归调用上述过程找到集合中的前个元素，返回
• 当时，在集合中递归调用上述过程，找到集合中的前个元素，返回

---

参考Haskell代码：

ksplit 0 xs = ([], xs)
ksplit k xs
    = let x = head xs
          xs1 = filter (<  x) xs
          xs2 = filter (== x) xs
          xs3 = filter (>  x) xs
          n1  = length xs1
          n2  = length xs2 + n1
          n3  = length xs3 + n2
      in  if k > length xs
          then error "not_enough_elements"
          else if k == n1
               then (xs1, xs2 ++ xs3)
               else if k == n2
                    then (xs1 ++ xs2, xs3)
                    else if k == n3
                         then (xs, [])
                         else if k < n1
                              then let (ys1, ys2) = ksplit k xs1
                                   in  (ys1, ys2 ++ xs2 ++ xs3)
                              else if k < n2 -- k \in (n1, n2)
                                   then (xs1 ++ take (k - n1) xs2, take (n2 - k) xs2 ++ xs3)
                                   else let (ys1, ys2) = ksplit (k - n2) xs3 -- k \in (n2, n3)
                                        in  (xs1 ++ xs2 ++ ys1, ys2)