基本使用與原理

std::sort 是一個模板函數(shù)，常見簽名如下：

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

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

• first，last：指定排序范圍的隨機訪問迭代器。
• comp：可選的比較器，定義元素順序，默認為 std::less（基于 operator< 的升序排序）。
• 時間復(fù)雜度：平均和最壞情況均為 O(n log n)。
• 空間復(fù)雜度：通常為 O(log n)，用于遞歸?；蚺R時緩沖區(qū)。
• 要求：比較器必須滿足嚴格弱序（strict weak ordering），否則可能導(dǎo)致未定義行為。

核心算法：內(nèi)省排序（Introsort）

C++ 標準未強制指定 std::sort 的實現(xiàn)算法，但大多數(shù)現(xiàn)代標準庫（如 libstdc++、libc++）采用 內(nèi)省排序（Introsort）。

Introsort 由 David Musser 于 1997 年提出，是一種混合排序算法，結(jié)合了快速排序（Quicksort）、堆排序（Heapsort）和插入排序（Insertion Sort）的優(yōu)點，以兼顧效率和魯棒性。

1. 快速排序

快速排序是 Introsort 的主要算法，步驟如下：

• 選擇基準（pivot）：通常使用三數(shù)取中（median-of-three，選取首、尾、中間元素的中位數(shù)）或隨機選擇。
• 分區(qū)（partition）：將元素分為小于等于基準和大于基準的兩部分。
• 遞歸：對兩個子區(qū)間遞歸排序。

特點：

• 平均時間復(fù)雜度：O(n log n)。
• 最壞情況（如已排序或逆序數(shù)組）：O(n²)。
• 優(yōu)化：三數(shù)取中或隨機化基準減少最壞情況概率。

實現(xiàn)細節(jié)：

• 分區(qū)方案：常用 Lomuto 或 Hoare 分區(qū)算法。
• 基準選擇：三數(shù)取中避免極端情況（如已排序輸入）。

2. 堆排序

當快速排序的遞歸深度超過閾值（通常為 2 * log n），Introsort 切換到堆排序，以避免快速排序的最壞情況。

步驟：

• 構(gòu)建最大堆（或最小堆，取決于排序順序）。
• 反復(fù)將堆頂元素移到末尾并調(diào)整堆。

特點：

• 時間復(fù)雜度：始終為 O(n log n)。
• 空間復(fù)雜度：O(1)（原地排序）。
• 適合處理快速排序退化的場景。

實現(xiàn)細節(jié)：

• 使用數(shù)組表示堆，通過下標計算父子節(jié)點關(guān)系。
• 堆調(diào)整（sift-down）確保堆性質(zhì)。

3. 插入排序

當子區(qū)間大小較小時（通常 < 16 或 32 個元素，具體閾值依實現(xiàn)而定），Introsort 切換到插入排序。

步驟：

• 逐個將元素插入到已排序的子序列中。

特點：

• 時間復(fù)雜度：O(n²)，但在小數(shù)組上常數(shù)開銷低。
• 適合部分有序或小規(guī)模數(shù)據(jù)。

實現(xiàn)細節(jié)：

• 通常通過循環(huán)實現(xiàn)，避免遞歸。
• 常用于優(yōu)化小規(guī)模子區(qū)間的排序。

原因：

• 快速排序：平均性能優(yōu)異，但在最壞情況下（如已排序或重復(fù)元素）退化為 O(n²)。
• 堆排序：保證最壞情況 O(n log n)，但平均性能稍遜，且堆調(diào)整開銷較高。
• 插入排序：在小規(guī)模數(shù)據(jù)上高效，減少遞歸開銷。 Introsort 動態(tài)切換算法，確保：
• 高效性：利用快速排序的平均性能。
• 魯棒性：通過堆排序避免最壞情況。
• 優(yōu)化性：插入排序處理小數(shù)組。

自定義排序

1. 函數(shù)指針

定義一個獨立的比較函數(shù)，簽名需為bool(T, T)：

bool compare(int a, int b) {
    return a > b; // 降序排序
}

std::vector<int> vec = {5, 2, 9, 1, 5};
std::sort(vec.begin(), vec.end(), compare); // 結(jié)果為 {9, 5, 5, 2, 1}

2. 靜態(tài)成員函數(shù)

在類中定義靜態(tài)比較函數(shù)，避免依賴對象實例：

class Sorter {
public:
    static bool compare(int a, int b) {
        return a > b; // 降序排序
    }
};

std::vector<int> vec = {5, 2, 9, 1, 5};
std::sort(vec.begin(), vec.end(), Sorter::compare);

注意：非靜態(tài)成員函數(shù)因隱含this指針，簽名不匹配std::sort的要求，因此無法直接使用。

3. 使用函數(shù)對象

通過定義一個類并重載operator()，可以在比較器中存儲狀態(tài)：

class Comparator {
    int threshold;
public:
    Comparator(int t) : threshold(t) {}
    bool operator()(int a, int b) const {
        return a > threshold && a < b; // 僅對大于threshold的元素降序排序
    }
};

std::vector<int> vec = {5, 2, 9, 1, 5};
std::sort(vec.begin(), vec.end(), Comparator(3));

4. 使用Lambda表達式（C++11及以上）

Lambda表達式提供了一種簡潔的方式定義比較器，并可捕獲外部變量：

int threshold = 3;
std::vector<int> vec = {5, 2, 9, 1, 5};
std::sort(vec.begin(), vec.end(), [threshold](int a, int b) {
    return a > threshold && a < b;
});

5.使用std::function

C++11引入的std::function可以包裝任何可調(diào)用對象（包括函數(shù)指針、Lambda、函數(shù)對象等），提供更靈活的方式：

#include <functional>
std::function<bool(int, int)> comp = [](int a, int b) {
    return a > b; // 降序排序
};

std::vector<int> vec = {5, 2, 9, 1, 5};
std::sort(vec.begin(), vec.end(), comp);

適用場景：當需要在運行時動態(tài)選擇比較器時，std::function非常有用，但會引入少量性能開銷。

6.使用標準比較器（如std::greater、std::less）

C++標準庫提供了預(yù)定義的比較器（如<functional>中的std::greater和std::less），可直接用于簡單排序需求：

#include <functional>
std::vector<int> vec = {5, 2, 9, 1, 5};
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序排序
std::sort(vec.begin(), vec.end(), std::less<int>());   // 升序排序

優(yōu)點：無需手動定義比較器，代碼簡潔，適合常見升序或降序需求。

7.重載operator<

對于自定義結(jié)構(gòu)體或類，可以通過重載operator<來定義默認排序規(guī)則，省去顯式比較器：

struct Person {
    std::string name;
    int age;
    bool operator<(const Person& other) const {
        return age < other.age; // 按年齡升序
    }
};

std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 20}};
std::sort(people.begin(), people.end()); // 使用operator<，按年齡升序

適用場景：當類型有自然的排序規(guī)則且不需要多種排序方式時，重載operator<是最簡潔的方案。

自定義結(jié)構(gòu)體或類的排序

當排序?qū)ο笫亲远x結(jié)構(gòu)體或類時，可以結(jié)合上述方法。

例如，使用Lambda：

std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 20}};

// 按名字字典序排序
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.name < b.name;
});

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論