問題描述：給定具有個(gè)元素的全序集合
撇眯，比較算符為
，求最大的
個(gè)元素锚国，不要求排序玄坦。下面按照取K個(gè)最小值的情況討論。
基本思想：類似于快速排序法豺总，選擇一個(gè)元素將其插入到數(shù)組的一個(gè)位置择懂，使得左側(cè)的元素都小于等于該標(biāo)記元素，右側(cè)元素都大于等于該元素表伦。
- 取第一個(gè)元素為標(biāo)記元素赂弓，掃描后續(xù)的元素，并與其比較翔怎，分為三類
- 一類是全部小于該元素杨耙，數(shù)組計(jì)為
，個(gè)數(shù)計(jì)為
- 一類是全部等于該元素容握，數(shù)組計(jì)為
剔氏，個(gè)數(shù)計(jì)為
- 一類是全部大于該元素，數(shù)組計(jì)為
羊苟，個(gè)數(shù)計(jì)為
- 定義
- 一類是全部小于該元素杨耙，數(shù)組計(jì)為
- 將
與
比較感憾，確定其位置。
- 當(dāng)
時(shí)凉倚，返回結(jié)果即
- 當(dāng)
時(shí)嫂沉，返回結(jié)果即
- 當(dāng)
時(shí)，返回結(jié)果即
集合本身
- 當(dāng)
時(shí)瓦胎，對
- 當(dāng)
時(shí)尤揣，在
個(gè)元素
北戏，返回
- 當(dāng)
時(shí)漫蛔，在
個(gè)元素
，返回
參考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)
