K個(gè)最大（最?。┰氐乃惴?/h2>

問題描述：給定具有個(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ì)為
  • 定義
• 將與比較，確定其位置。
• 當(dāng)時(shí)，返回結(jié)果即
• 當(dāng)時(shí)，返回結(jié)果即
• 當(dāng)時(shí)，返回結(jié)果即集合本身
• 當(dāng)時(shí)，對(duì)集合遞歸調(diào)用上述過(guò)程
• 當(dāng)時(shí)，在集合中遞歸調(diào)用上述過(guò)程找到集合中的前個(gè)元素，返回
• 當(dāng)時(shí)，在集合中遞歸調(diào)用上述過(guò)程，找到集合中的前個(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)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。