nth_element是如何實現的？

Question

有很多在計算器上索賠和其他地方nth_element是O（n）的，它通常與Introselect實現：http://en.cppreference.com/w/cpp/algorithm/nth_element

我想知道如何可以做到這一點。我看着Wikipedia's explanation of Introselect，這讓我更加困惑。算法如何在QSort和Mediology中間值之間切換？

我發現內省排序文件位置：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf但是，上面寫着：

在本文中，我們專注於分類問題，在後面的部分返回到選擇問題只是暫時。

我試過通過STL本身來了解nth_element是如何實現的，但那真是太快了。

有人可以向我展示如何實現Introselect的僞代碼？或者甚至更好，實際的C++代碼，當然除了STL以外:)

Answer 1

你問了兩個問題，有名無實的一個

如何nth_element實施？

，你已經回答了：

有很多在計算器上索賠和其他地方nth_element是O（n），它通常與Introselect實現。

我也可以通過查看我的stdlib實現來確認。 （更多關於這個版本）。

而且一個地方，你不明白的答案：

如何快速排序中位數中位數的和之間的算法開關？

讓我們看看在僞代碼，我從我的STDLIB提取：

nth_element(first, nth, last) 
{ 
    if (first == last || nth == last) 
    return; 

    introselect(first, nth, last, log2(last - first) * 2); 
} 

introselect(first, nth, last, depth_limit) 
{ 
    while (last - first > 3) 
    { 
     if (depth_limit == 0) 
     { 
      // [NOTE by editor] This should be median-of-medians instead. 
      // [NOTE by editor] See Azmisov's comment below 
      heap_select(first, nth + 1, last); 
      // Place the nth largest element in its final position. 
      iter_swap(first, nth); 
      return; 
     } 
     --depth_limit; 
     cut = unguarded_partition_pivot(first, last); 
     if (cut <= nth) 
     first = cut; 
     else 
     last = cut; 
    } 
    insertion_sort(first, last); 
} 

沒有進入關於引用功能heap_select和unguarded_partition_pivot，我們可以清楚地看到細節，即nth_element給introselect 2 * log2(size)細分步驟（在快速選擇最佳情況下需要兩倍），直到heap_select開始並解決問題。

Answer 2

聲明：我不知道std::nth_element是如何在任何標準庫中實現的。

如果您知道Quicksort的工作方式，您可以輕鬆修改它以完成此算法所需的工作。 Quicksort的基本思想是在每一步中，將數組分成兩部分，使得所有小於主元的元素都在左子數組中，並且所有等於或大於主元的元素都在右子數組中。 （修改Quicksort稱爲三元Quicksort，創建第三個子數組，其元素與主元相等，然後右子數組只包含嚴格大於主元的元素。）然後Quicksort遞歸排序左和右子元素-arrays。

如果你只想在ñ個元素移動到位，而不是遞歸到既子陣列，你可以在每一步告訴你是否需要將下降到左邊或右邊子陣列。 （你知道這是因爲n排序數組中的第n個元素的索引爲n所以它成爲一個比較索引的問題。）所以 - 除非你的Quicksort受到最壞情況的退化 - 你將剩下的大小減半數組在每一步。 （你從來不看其他子陣列一次。）因此，平均來說，你正在處理中的每個步驟以下長度的數組：

1. Θ（ñ）
2. Θ（ñ/2）
3. Θ（ñ/4）
4. ...

每一步在處理數組的長度上都是線性的。 （你循環一次，並根據它與樞軸的比較來決定每個元素應該去哪個子數組。）

你可以看到，在經過Θ（log（N））步後，我們最終會到達一個單例數組並完成。如果你總結N（1 + 1/2 + 1/4 + ...），你會得到2 N。或者，在平均情況下，因爲我們不能希望這個關鍵點總是正好是中位數，所以這個數字大約是Θ（N）。

Answer 3

從STL代碼（3.3版，我認爲）是這樣的：

template <class _RandomAccessIter, class _Tp> 
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 
        _RandomAccessIter __last, _Tp*) { 
    while (__last - __first > 3) { 
    _RandomAccessIter __cut = 
     __unguarded_partition(__first, __last, 
          _Tp(__median(*__first, 
             *(__first + (__last - __first)/2), 
             *(__last - 1)))); 
    if (__cut <= __nth) 
     __first = __cut; 
    else 
     __last = __cut; 
    } 
    __insertion_sort(__first, __last); 
} 

讓我們簡化一下：

template <class Iter, class T> 
void nth_element(Iter first, Iter nth, Iter last) { 
    while (last - first > 3) { 
    Iter cut = 
     unguarded_partition(first, last, 
          T(median(*first, 
            *(first + (last - first)/2), 
            *(last - 1)))); 
    if (cut <= nth) 
     first = cut; 
    else 
     last = cut; 
    } 
    insertion_sort(first, last); 
} 

我做什麼這裏是去除雙下劃線和_Uppercase東西，這只是爲了保護用戶可以合法定義爲宏的代碼。我還刪除了最後一個參數，該參數僅用於模板類型推導，並且爲了簡潔起見將其重命名爲迭代器類型。

正如您現在應該看到的那樣，它會重複劃分範圍，直到剩餘範圍內剩餘的元素少於四個，然後對其進行簡單排序。

現在，爲什麼是O（n）？首先，最多三個元素的最終排序是O（1），因爲最多三個元素。現在，剩下的是重複分區。分區本身是O（n）。儘管如此，每一步都會減少下一步需要觸及的元素的數量，因此您有O（n）+ O（n/2）+ O（n/4）+ O（n/8），這就是小於O（2n），如果你總結。由於O（2n）= O（n），因此平均具有線性複雜性。