深度剖析std::sort

一、簡介

std::sort是C++ STL的一個排序算法，它可以按照一定規則對一個給定的數組、向量或迭代器範圍內的元素進行排序。std::sort是非穩定排序算法，平均時間複雜度為O(nlogn)，最壞情況下時間複雜度為O(n^2)，空間複雜度為O(logn)。

二、語法

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

sort接受兩個迭代器參數，第一個迭代器first表示要排序的範圍中的第一個元素，last表示最後一個元素的下一個位置。sort可以通過比較器comp自定義排序規則。

三、排序規則

std::sort默認按照小於號運算符（operator<）進行比較，也就是說，排序後的元素是按照從小到大的順序排列的。如果想要對元素按照從大到小的順序排序，可以自定義比較器：

bool cmp(int a, int b) {
    return a > b;
}
std::sort(a.begin(), a.end(), cmp);

上面的代碼定義了一個比較器cmp，將a中的元素按照從大到小的順序進行排序。

四、分區策略

std::sort採用的是快速排序（quicksort）的分區策略。簡單來說，快速排序的過程就是先選出一個元素作為基準（pivot），將比pivot小的元素放在左邊，比pivot大的元素放在右邊，然後遞歸排序左右兩個子序列。

std::sort是一種不穩定排序算法，排序後相等的元素在數組中的相對位置可能會發生變化。這是因為std::sort的分區策略採用的是最後一個元素作為基準，而不是中間的元素或者隨機選擇的元素。如果存在相等的元素，std::sort在分區時很可能會導致相等的元素被分配到不同的子序列中。

五、優化

1. 優化比較器

std::sort在每一次比較時都要調用比較器函數，因此比較器函數的效率對排序的性能有很大影響。可以採用lambda函數或者函數對象的方式對比較器進行優化：

std::sort(a.begin(), a.end(), [](int a, int b) {
    return a > b;
});

上面的代碼使用lambda函數定義了一個比較器，實現了對a的降序排序。

2. 優化部分排序

如果只需要對序列中的一部分進行排序，可以使用partial_sort函數，比直接使用sort要快一些：

std::partial_sort(a.begin(), a.begin() + k, a.end());

上面的代碼對a中前k個元素進行排序，後面的元素不保證有序。此時，partial_sort的時間複雜度為O(nlogk)，比sort快了一些。

六、示例

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

int main() {
    std::vector<int> a = {3, 1, 2, 5, 4};
    std::sort(a.begin(), a.end());
    for (auto it : a) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    std::sort(a.begin(), a.end(), [](int a, int b) {
        return a > b;
    });
    for (auto it : a) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    std::partial_sort(a.begin(), a.begin() + 3, a.end());
    for (auto it : a) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    return 0;
}