问题描述：给定具有个元素的全序集合
，比较算符为
，求最大的
个元素，不要求排序。下面按照取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)
