C++中std::partial_sort的使用小結

更新時間：2025年04月07日 11:15:11 作者：點云SLAM

std::partial_sort?是?C++?標準庫中的一個算法,它可以對容器中的一部分元素進行排序,本文主要介紹了C++中std::partial_sort的使用小結,感興趣的可以了解一下

std::partial_sort 是 C++ 標準庫中的一個算法，它可以對容器中的一部分元素進行排序，使得前 N 個元素按順序排列，而不保證剩余部分有序。它的時間復雜度為 O(N log N + (M-N))，其中 M 是整個范圍的大小，N 是要排序的元素數量。

1. 語法

#include <algorithm>

template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

first：要排序的范圍的起始迭代器。
middle：指定排序后的前 N 個元素的終點，即 first + N。
last：排序范圍的結束迭代器。
comp（可選）：自定義比較函數。

2. 基本用法

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {7, 3, 9, 1, 6, 2, 8, 5, 4};

    // 僅對前 5 個元素排序
    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end());

    // 輸出前 5 個排序后的元素
    std::cout << "前 5 個最小的元素: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << "\n";

    // 輸出整個數組
    std::cout << "整個數組: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

輸出

前 5 個最小的元素: 1 2 3 4 5
整個數組: 1 2 3 4 5 9 8 7 6

注意：前 5 個元素是有序的，但整個數組仍然是部分無序的。

3. 使用自定義比較函數

可以使用 std::greater<int>() 進行降序排序：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {7, 3, 9, 1, 6, 2, 8, 5, 4};

    // 獲取前 5 個最大的元素（降序）
    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end(), std::greater<int>());

    // 輸出前 5 個排序后的元素
    std::cout << "前 5 個最大的元素: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

輸出

前 5 個最大的元素: 9 8 7 6 5

4. 與 std::sort 和 std::nth_element 的比較

算法	作用	復雜度	適用場景
std::sort	全部排序	O(N log N)	需要排序整個序列
std::partial_sort	僅保證前 N 個元素有序	O(N log N + (M-N))	只需要最小/最大 N 個有序元素
std::nth_element	只保證 N 處的元素正確，左側比它小，右側比它大	O(M)	只需要找到第 N 小的元素，且不關心其他元素順序