【算法】第 n 小數 nth_element

stl 中取第 n 小數的算法 nth_element 的函數原型如下

算法說明：

1、功能：執行 nth_element 後，nth 所指位置的元素将是整個區間有序時在該處的元素。對 [first, nth) 中的任意疊代器 i 和 [nth, last) 中的任意疊代器 j，滿足 !(*i > *j)。

2、要求：randomaccessiterator 必須滿足 valueswappable。*first 的類型必須滿足 moveconstructible 和 moveassignable。

3、複雜度：平均為線性。

源碼如下：

其中的  和 在之前介紹過，這裡不再列出它們的源碼。

函數中的 first 和 last 可能改變，當 [first, last) 區間大于3時就一直劃分，劃分是采用三者取中的方式以緩解輸入時的糟糕情況，每次劃分後産生兩段，若右段起點 cut <= nth，則再對右段劃分，否則對左段劃分。直到區間長度小于等于3時，索性對這個小區間進行插入排序，注意 nth 始終在 [first, last) 中。