C++ partial_sort(STL partial_sort)排序演算法詳解

通過範例很容易理解什麼是部分排序。假設有一個容器，它儲存了 100 萬個數值，但我們只對其中最小的 100 個感興趣。可以對容器的全部內容排序，然後選擇前 100 個元素，但這可能有點消耗時間。這時候需要使用部分排序，只需要這些數中的前100個是有序放置的。

對於部分排序，有一個特殊的演算法 partial_sort()，它需要 3 個隨機存取疊代器作為引數。如果這個函數的引數是 first、second 和 last，那麼這個演算法會被應用到 [first，last) 這個範圍內的元素上。執行這個演算法後，[first，second) 會包含降序序列 [first，last) 中最小的 second-first 個元素。

注意，在這個範例中，有一種之前沒遇到過的表示方式 [first，last)，用它來表示一個元素段，這是一個來自於數學領域的用來定義數位範圍的概念——區間。這兩個值叫作結束點，在這種表示法中，方括號表示包含相鄰的結束點，圓括號表示相鄰的結束點不包括在內。 例如，如果 (2，5) 是一個整數區間，2 和 5 都被排除在外，所以它只表示整數 3 和 4；這也被叫作開區間，因為兩個結束點都不包含。區間 [2，5) 包含 2 但不包含 5，所以它表示 2、3 和 4。（2，5] 表示 3、4 和 5。[2,5] 表示 2、3、4、5，並且它被叫作閉區間，因為包含了兩個結 束點。當然，first 和 last 都是疊代器，並且 [first，last) 表示包含 first 指向的元素而不包含 last 指向的元素，所以可以用它準確表示 C++ 中的範圍。

下面這段程式碼演示了 partial_sort() 演算法的工作方式：

size_t count {5}; // Number of elements to be sorted
std::vector<int> numbers {22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10};
std::partial_sort(std::begin(numbers), std::begin(numbers) + count, std::end(numbers));

執行partial__sort()後的效果如圖 1 所示。

---