我幾乎已經理解了許多STL演算法，直到我到達演算法std::nth_element。我被卡住了，我不知道它是如何作業的，也不知道它到底是怎么做的。
為了教育和理解，誰能給我解釋一下std::nth_element演算法是如何作業的？
std:: vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v. begin() 2, v.end()) 。
for (auto i : v)
std::cout << i << " "/span>;
std::cout <<'
'。
輸出：
1 0 2 3 6 7 8 5 4 9
- 那么這里的
nth元素在哪里？ - 該演算法如何以及做什么？
- 它是否做了某種部分排序？
下面是來自cppreference.com的一些解釋：
nth_element是一種部分排序演算法，它在[first, last]中重新排列元素，以便：
- 第n個指向的元素被改變為如果[first, last]被排序的話會出現在該位置的任何元素。
- 這個新的第n個元素之前的所有元素都小于或等于新的第n個元素之后的元素。
更正式地說，nth_element以升序對范圍[first, last]進行部分排序，以便對范圍[first, nth]中的任何i和范圍[nth, last]中的任何j滿足條件
!(*j < *i)（對于第一個版本，或comp(*j, *i) == false）。放在第n個位置的元素正是在這個位置出現的元素，如果這個范圍被完全排序的話。
第n個可能是終端迭代器，在這種情況下，該函式沒有任何作用。
- 我仍然對此感到困惑。什么是第n個元素，如何實作這樣一個可能的演算法？為了教育，我已經模仿了許多STL演算法。非常感謝！
uj5u.com熱心網友回復：
那么這里的第n個元素在哪里呢？
第n個元素是索引
2的2，因為這是你在傳遞begin() 2時要求的。如果對[first, last)進行排序，第n個指向的元素將被改為該位置上的任何元素。
這意味著，如果矢量被排序，元素的順序將是
0 1 2 3 4 5 6 7 8 9 ^--- begin() 2你要求將第三大元素放在索引2（第三位置），這就是演算法的作用。
此外，它將所有較小的元素放在前面，所有較大的元素放在后面：
! (*j < *i)(對于第一個版本，或者comp(*j, *i) == false對于第二個版本)，對于范圍[first, nth]中的任何i和范圍[nth, last]中的任何j都滿足。讓我們使用索引而不是迭代器，那么對于任何
i < 2和任何j > 2來說，可以認為v[i] < v[j]/code>。換句話說，1和0都比2 3 6 7 8 5 4 9中的任何元素小。uj5u.com熱心網友回復：
在討論你的問題之前，我先解釋一下我的代碼
例如我有這樣的代碼int m_array_biasa[8] {3,2, 10,45,33,56,23,47}。而我通常使用它，就像
一樣std::nth_element(m_array_biasa, m_array_biasa 4, m_array_biasa 8) 。所以這里的第n個元素是4[33]，std::nth_element的規則是，nth左邊的數字必須小于或等于，右邊的數字必須大于nth
。而且不要忘了，資料必須從小到大排序（默認）所以，原來的資料
3,2,10,45,33,56,23,47
改變為
2 3 10 23 33 45 47 56
我的nth是4[33]，所以上述規則適用（不包括排序的結果）
而結果是
3 2 10 23 33 56 45 47
注意上面，位置33沒有改變，但有時會有點混亂，例如我們把33改為1，那么結果是
2 1 3 10 23 45 47 56
這里發生了什么，為什么數字1會移動（被23取代），為什么它不像之前的數字33一樣，我之前說過，我們必須先對資料進行排序（見上面的排序），結果發現索引nth[4]是數字23，然后數字1被替換成數字23，為什么要替換呢，見第n_元素規則
。現在開始討論你的問題。
std:: vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 }; std::nth_element(v.begin(), v. begin() 2, v.end()) 。v.begin()包含9，v.begin() 2包含6，記住，nth_element會先排序
。0 1 2 3 4 5 6 7 8 9
而你的輸出是
1 0 2 3 6 7 8 5 4 9
上面的nth[2]（根據你的v.begin() 2）p是2，所以2在這里就像其他資料的參考，2之前的資料必須小于它，而2之后的資料必須大于它
。轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/326063.html
標籤：
上一篇：卡片游戲 基礎c語言試題