如何在 C++ 標準模板庫 (STL) 中排序

使用 C++ 標準函式庫中來自 <algorithm> 的 sort() 函式，將陣列或向量就地排序。預設情況下，它按升序對從 first 到（但不包括）last 的半開區間進行排序。傳遞一個比較器以選擇其他排序方式。

使用 sort() 函式在 C++ 中對陣列或向量進行排序

std::sort 接受隨機存取迭代器，因此它適用於陣列和向量。它無法就地重新排列 std::set 或 std::map，因為這些容器不提供隨機存取迭代器。這個完整的程式同時對陣列和向量進行排序：

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

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin 和 std::end 提供陣列的範圍，而向量使用它的 begin() 和 end() 迭代器。這個程式作為未執行的範例提供;在設定的執行環境中觀察到其輸出之前，輸出被省略。這兩個呼叫都會修改原始元素，因此後續程式碼會以新的順序看到它們。若只對容器的一部分進行排序，請傳遞界定該部分的迭代器。

在 C++ 中按降序對陣列或向量進行排序

將 std::greater<> 作為第三個引數傳遞，以將值從最大到最小排序。為比較器包含 <functional>。例如，std::sort(values.begin(), values.end(), std::greater<>{}); 以降序對向量進行排序。比較器改變排序規則，而不改變排序的範圍。

使用 partial_sort() 對陣列或向量的一部分進行排序

當只有字首需要排序時，使用 partial_sort(first, middle, last)。它將最小的 middle - first 個元素以排序順序放在 middle 之前。從 middle 到 last 的元素不保證有任何特定的順序。例如，std::partial_sort(values.begin(), values.begin() + 3, values.end()); 為前三個位置選擇三個最小值。

在 C++ 中使用帶有 sort() 的自訂比較器

比較器可以讓你按諸如字串長度之類的鍵對值進行排序。例如，std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); 將較短的字串放在前面。比較器必須定義一個嚴格弱序:它必須是一致的，並且不得認為某個項目在它自身之前。在此比較下，長度相等的字串是等價的，因此它們的相對順序未指定。使用此範例時，將 <string> 與 <algorithm> 一同包含。

使用 is_sorted() 檢查範圍是否已排序

當從 first 到（但不包括）last 的範圍按預設比較排序時，std::is_sorted(first, last) 傳回 true，否則傳回 false。它檢查範圍而不重新排列其元素。在檢查自訂排序時，提供用於該排序的相同比較器，如 std::is_sorted(words.begin(), words.end(), compare) 中所示。

排序演算法的時間複雜度

對於 std::sort，標準規定在最壞情況下進行 O(N log N) 次比較，其中 N 是範圍中的元素數。這描述了工作量如何隨範圍長度增長;它不承諾任何特定的排序實作。std::partial_sort 在從 N 個元素中選擇和排序 K 個元素時使用大約 N log K 次比較，而 std::is_sorted 最多進行 N - 1 次比較。這些界限有助於區分完全對一個範圍進行排序、僅對字首進行排序或檢查現有順序。