快捷導(dǎo)航

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

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

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

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

如果兩個(gè)元素相等（比較結(jié)果為等價(jià)），排序后它們的相對(duì)順序與原序列中保持一致。

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

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

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

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

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

4、小結(jié)

std::sort：更快、更省內(nèi)存，但不保證穩(wěn)定性。
std::stable_sort：稍慢、更耗內(nèi)存，但保證穩(wěn)定性。
一句話：性能優(yōu)先用 sort，順序敏感用 stable_sort。
備注：對(duì)于頻繁排序的小型容器，可考慮使用 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; // 成績(jī)相同時(shí)按名字升序
}

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 保證同分學(xué)生順序不變
        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{
        // 對(duì)于頻繁排序的小型容器，可考慮使用 std::list::sort()（穩(wěn)定且鏈表友好）
        std::list<Student> studentList;
        for (const auto& s : studentArray){
            studentList.push_back(s);
        }

        // 使用 std::list::sort() 進(jìn)行排序
        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;
}