C++ 標準庫 sort() / stable_sort() / partial_sort() 對比

C++ STL標準庫中提供了多個用於排序的Sort函數，常用的包括有sort() / stable_sort() / partial_sort(),具體的函數用法如下表所示：

1. std::sort(first,last)

std::sort()是STL標準庫提供的模板函數，用於對容器或者數組中指定的範圍（first~last）元素進行排序，預設的排序方法是以元素的值的大小做升序排序，同時也可以指定其他的排序規則（如std::greater）,也可以自定義排序規則。

std::sort()函數底層基於快速排序進行實現，時間複雜度為N * log(N)，因此需要容器或者數組註意以下幾點：

• 容器的迭代器必須是隨機訪問迭代器，如std::array、std::vector、std::deque。
• 如果採用預設的升序排序方法，則元素必須支持operate<運算符。
• 自定義類對象容器使用std::sort()排序時，因為需要交換位置，所以必須提供拷貝構造函數和賦值運算符。
• std::sort()無法保證相同元素的原始位置，這裡的相同是指進行比較的結果為相等，而對象本身不相同。如果需要保持相對順序相同，則應該使用std::stable_sort()

不同庫對std::sort()的實現：libstdc++和libc++.

示例代碼：

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

using namespace std;
void Print(std::string message,const std::vector<int>& vec)
{
    cout << message << ": ";
    for(const auto c : vec)
	cout << c << " ";
    cout <<endl;
}

int main()
{
    std::vector<int> myVector{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    // 1. 以預設的排序規則
    std::sort(myVector.begin(),myVector.end());
    Print("Sorted Default", myVector);
    // 2. 以標準庫的greater函數進行排序
    std::sort(myVector.begin(),myVector.end(),std::greater<int>());
    Print("Sorted Standard Compare Function",myVector);
    // 3.以自定義的函數定義排序規則
    // lamda 表達式
    auto cmp1 = [](const int a,const int b)
    {
        return a < b;
    };
    std::sort(myVector.begin(),myVector.end(),cmp1);
    Print("Sorted Lamda Function",myVector);
    // 可調用對象
    struct
    {
        bool operator()(const int a,const int b){return a > b;}
    } cmp2;
    std::sort(myVector.begin(),myVector.end(),cmp2);
    Print("Sorted Function Object",myVector);
	
    return 0;
}

輸出結果為：

Sorted Default : 0 1 2 3 4 5 6 7 8 9
Sorted Standard Compare Function : 9 8 7 6 5 4 3 2 1 0
Sorted Lamda Function : 0 1 2 3 4 5 6 7 8 9
Sorted Function Object : 9 8 7 6 5 4 3 2 1 0

2. std::stable_sort(first,last)

使用std::sort()的一個問題是在排序時，無法保證值相等時的元素相對位置保持不變，如果程式中對相對順序有要求，那麼就需要使用std::stable_sort(),這是對std::sort()的一個升級版本，調用的方式和std::sort()相同，但是可以保證排序後的結果能夠保持原有的相對順序。

std::stable_sort()底層是基於歸併排序，時間複雜度是N * log(N)^2,如果可以使用額外的記憶體空間，那麼時間複雜度可以降低為N * log(N),std::sort()對容器和數組的要求與std::sort()相同。

不同庫對std::stable_sort()的實現：libstdc++和libc++.

3. std::partial_sort(first,middle,last)

上述的std::sort()和std::stable_sort()都是對所選的範圍內的所有數據進行排序，但是如果對於一個容器或者數組，我們只需要找到其最小的幾個元素，那麼採用全局排序的方法效率將會很低，尤其是容器中的元素數量非常大時，將會對性能產生很大的影響。因此，C++標準庫提供了std::partial_sort()函數，來應用於這種場景。

std::partial_sort()函數的功能從其名字就可以得到，可以理解為部分排序，即從元素區間範圍內取出部分元素進行排序。函數參數列表中first，last表示元素範圍，middle用於定義需要進行排序的元素個數，具體的，std::partial_sort()會將範圍first-last範圍內最小（大）的middle-first個元素移動到first~middle範圍，並對這些元素進行升（降）序排序。

std::partial_sort()底層採用堆排序，時間複雜度為N * log(M),其中N為last-first,M為middle-first。由於底層實現的限制，std::partial_sort()對容器的要求與std::sort()和std::stable_sort()相同。

不同庫對std::stable_sort()的實現：libstdc++和libc++.

示例代碼：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
void Print(std::string message,const std::vector<int>& vec)
{
    cout << message << ": ";
    for(const auto c : vec)
	cout << c << " ";
    cout <<endl;
}

int main()
{
    std::vector<int> myVector{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    // 1. 以預設的排序規則
    std::partial_sort(myVector.begin(),myVector.begin() + 4,myVector.end());
    Print("Sorted Default", myVector);
    // 2. 以標準庫的greater函數進行排序
    std::partial_sort(myVector.begin(),myVector.end(),std::greater<int>());
    Print("Sorted Standard Compare Function",myVector);
    // 3.以自定義的函數定義排序規則
    // lamda 表達式
    auto cmp1 = [](const int a,const int b)
    {
        return a < b;
    };
    std::sort(myVector.begin(),myVector.end(),cmp1);
    Print("Sorted Lamda Function",myVector);
	
    return 0;
}

Sorted Default: 0 1 2 3 8 7 6 9 5 4
Sorted Standard Compare Function: 9 8 7 6 5 0 1 2 3 4
Sorted Lamda Function: 0 1 9 8 7 6 5 2 3 4

* C#中的Array.Sort()

筆者在用C++復刻C#代碼的時候發現對相同的數組排序的結果有時候會出現不一致，查了C#的官方文檔後才發現，C#中Array.Sort()函數是unstable_sort,也就是說其排序是無法保證相對順序的，而且Array似乎也沒有提供Stable_Sort版本的排序函數，因此如果需要保證相對順序不變，需要手動給原始的數據添加一個index,這樣再其他的key判等都相等時可以採用額外的Index來保持相對的原始序。而且有意思的是，Array.Sort()函數具體使用的排序方法是根據數據規模發生改變的

-如果數據量小於等於16個，則採用插入排序
-如果需要排序的數量超過2 * log(N)，其中N為輸入的排序範圍，則採用堆排序
-其餘情況均採用快速排序

以上是對常用的標準庫排序演算法的總結和不同語言的對比，可以根據實際需要和數據量的大小來選擇合適的排序演算法。