C++?sort()與stable_sort()使用指北(附示例代碼)

更新時間：2025年12月22日 10:35:18 作者：hellokandy

這篇文章主要介紹了C++?sort()與stable_sort()使用的相關資料,std::sort()和std::stable_sort()都是C++標準庫中的排序算法,文中通過代碼將用法介紹的非常詳細,需要的朋友可以參考下

1、排序的穩(wěn)定性是個什么玩意

如果兩個元素相等（比較結果為等價），排序后它們的相對順序與原序列中保持一致。

2、到底誰更穩(wěn)定

std::sort() 是不穩(wěn)定的排序算法，意味著相等元素的相對順序在排序后可能被改變。
std::stable_sort() 是穩(wěn)定排序，保證相等元素的原始輸入順序在排序后保持不變。

3、它們內部的實現(xiàn)方式

std::sort() 通常采用Introsort（內省排序），結合快速排序、堆排序和插入排序，平均性能極佳。
std::stable_sort() 多基于歸并排序（Merge Sort），因其天然具備穩(wěn)定性，適合分治策略下的有序合并。

盡管 stable_sort() 提供了穩(wěn)定性保障，但其代價是更高的內存消耗和潛在的性能下降（尤其在大數(shù)據(jù)集上）。對于金融系統(tǒng)、考試排名、事件日志等場景，穩(wěn)定性是硬性需求，應無條件選用 stable_sort()。

4、小結

std::sort：更快、更省內存，但不保證穩(wěn)定性。
std::stable_sort：稍慢、更耗內存，但保證穩(wěn)定性。
一句話：性能優(yōu)先用 sort，順序敏感用 stable_sort。
備注：對于頻繁排序的小型容器，可考慮使用 std::list::sort()

5、示例代碼

#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>//sort

using std::vector;
using std::list;
using std::string;

struct Student
{
    string name;
    double score;
    Student(const string &n, double s) : name(n), score(s) {}
    // 重載 operator< 以按score升序排序(list::sort)
    bool operator<(const Student& other) const {
        return score < other.score;
    }
};

bool CompareByScore(const Student& a, const Student& b) {
    return a.score > b.score; // 降序
}
//
bool CompareStudent(const Student& a, const Student& b) {
    if (a.score != b.score){
        return a.score < b.score;
    }
    return a.name < b.name; // 成績相同時按名字升序
}

int main(int argc, char *argv[])
{
    std::vector<Student> studentArray = {
        {"Candy", 91.0},
        {"Body", 91.0},
        {"Andy", 91.0},
        {"Lucy", 91.0},
        {"Lily", 90.5},
        {"Luck", 92.5},
        {"Kandy", 95.0},
    };

    do{
        std::cout << "v1: std::sort" << std::endl;
        auto v1 = studentArray;
        std::sort(v1.begin(), v1.end(), [](const Student &a, const Student &b){
            return a.score > b.score;//降序
        });
        for (const auto& s : v1) {
            std::cout << s.name << ": " << s.score << "\n";
        }
    }while(false);


    do{
        // 使用 stable_sort 保證同分學生順序不變
        std::cout << "\nv2: std::stable_sort" << std::endl;
        auto v2 = studentArray;
        std::stable_sort(v2.begin(), v2.end(), CompareByScore);
        for (const auto& s : v2) {
            std::cout << s.name << ": " << s.score << "\n";
        }
    }while(false);


    do{
        // 對于頻繁排序的小型容器，可考慮使用 std::list::sort()（穩(wěn)定且鏈表友好）
        std::list<Student> studentList;
        for (const auto& s : studentArray){
            studentList.push_back(s);
        }

        // 使用 std::list::sort() 進行排序
        std::cout << "\nlist1: sort" << std::endl;
        auto list1 = studentList;
        list1.sort();                 // 使用 operator<
        for (const auto& s : list1) {
            std::cout << s.name << ": " << s.score << "\n";
        }

        //使用自定義比較函數(shù)
        std::cout << "\nlist2: CompareStudent" << std::endl;
        auto list2 = studentList;
        list2.sort(CompareStudent);
        for (const auto& s : list2) {
            std::cout << s.name << ": " << s.score << "\n";
        }
    }while(false);

    return 0;
}