排序工具箱：sort、stable_sort与partial_sort轻松上手

你每天都会遇到排序——比如老师把全班同学的考试卷按分数从高到低排列，你整理自己的零花钱按面额排好，或者游戏里查看排行榜前10名。在编程中，排序更是家常便饭，C++的STL和Python都为我们提供了强大的排序工具。今天我们就来认识三个最常用的排序算法：sort（快排）、stable_sort（稳定排序）和partial_sort（部分排序），它们就像三个不同风格的整理箱，能帮你快速把数据收拾得井井有条。

1. sort —— 暴力高效的全排序

生活中：你想把书架上所有书本按拼音顺序排好，不管它们原来的位置，快速把全部书整理一遍。就像 sort 一口气搞定所有元素。

原理：C++的 sort 底层通常使用内省排序（Introsort），它结合了快速排序、堆排序和插入排序的优点，平均时间复杂度 O(n log n)，最坏情况也是 O(n log n)（比起朴素快排的 O(n²) 安全得多）。它不稳定——意思是如果两个元素相等，它们的相对顺序可能会改变。

用法：

#include <algorithm>          // 包含排序算法

int scores[100];              // 假设有100个学生的考试成绩
sort(scores, scores + 100);   // 升序排列（默认）

vector<int> heights;          // 全班同学的身高
sort(heights.begin(), heights.end());                     // 升序
sort(heights.begin(), heights.end(), greater<int>());     // 降序，greater<int>() 是预定义的比较对象

自定义排序：比如按成绩的个位数从小到大排（有点奇怪，但能演示自定义）：

bool compareByUnit(int a, int b) {
    return (a % 10) < (b % 10);   // 个位数小的在前
}
sort(scores, scores + 100, compareByUnit);

生活例子：班级有30个同学，学号是随机的，你想按学号从小到大排好座位。直接用 sort(student_ids, student_ids+30) 就能快速搞定。如果两个同学学号相同（理论上不会），sort 不保证谁先谁后，但学号一般唯一，所以没关系。

2. stable_sort —— 细心稳定的排序

生活中：你有一摞作业本，先按班级分组（A班在前，B班在后），再按姓名拼音排序。如果同一班级里有同名同姓的同学，你想保持他们原来的前后顺序（比如先交作业的排前面）。这时候就需要稳定排序——stable_sort 能保证相等元素的相对位置不变。

原理：stable_sort 通常基于归并排序的稳定版本，时间复杂度也是 O(n log n)，但会额外占用 O(n) 的临时内存（或者 O(log n) 的递归栈空间）。它保证稳定性，所以适合多重排序。

用法：

struct Student {
    string name;   // 姓名
    int grade;     // 年级（1~6）
};

vector<Student> students;
// 先按年级升序（稳定）
stable_sort(students.begin(), students.end(),
            [](const Student& a, const Student& b) {
                return a.grade < b.grade;
            });
// 再按姓名升序（稳定，这样同年级的学生会按照姓名排序，而姓名相同的会保留原顺序）
stable_sort(students.begin(), students.end(),
            [](const Student& a, const Student& b) {
                return a.name < b.name;
            });

生活例子：运动会成绩单上，先按班级排序，再按成绩排序。如果两个学生同班且成绩相同，我们需要显示他们原来的报名顺序（比如张三先报名，李四后报名）。这时候用两次 stable_sort 就能完美实现。

注意：sort 和 stable_sort 的用法几乎一样，只是稳定性不同。大多数时候用 sort 就够快，只有当排序中包含“相等元素要保持原始顺序”的需求时，才用 stable_sort。

3. partial_sort —— 只关心前几名

生活中：你只想知道全班身高最高的3个人是谁，其他人不管顺序。或者你想看成绩的前5名，后面的第6到第100名随便排。这就是 partial_sort 的用武之地。

原理：partial_sort 会把容器中最小的（默认）m 个元素放到前面，并且这 m 个元素内部有序，其余元素不保证任何顺序。它的时间复杂度是 O(n log m)，当 m 远小于 n 时，效率极高（比如从10000个数字里找最小的10个，比全部排序快很多）。内部使用堆结构。

用法：

vector<int> scores = {78, 92, 65, 88, 73, 91, 55, 84, 79, 60};
// 想知道最低的3个分数（升序取前3个最小的）
partial_sort(scores.begin(), scores.begin() + 3, scores.end());
// 结果：scores 的前3个元素是 55, 60, 65（有序），后面的 78, 92, 88 ... 顺序不定

生活例子：周末去超市，你想买最便宜的3个零食（价格分别是：5, 8, 3, 10, 2, 7）。用 partial_sort 就能立刻知道最便宜的三个是 2, 3, 5 元。其他零食的价格你不用管。

Python 中的替代：Python 没有直接的 partial_sort，但可以用 heapq.nsmallest 或 heapq.nlargest 来获取最小的/最大的 m 个元素（返回一个新的有序列表），这实际上就是部分排序的常用场景。

import heapq
prices = [5, 8, 3, 10, 2, 7]
cheapest_3 = heapq.nsmallest(3, prices)  # 返回 [2, 3, 5]

四种算法一张表看懂

算法	比喻	稳定性	时间复杂度	适用场景
sort	暴力整理全部书籍	不稳定	O(n log n)	普通全排序，不关心等值顺序
stable_sort	细心整理，同名书保持原序	稳定	O(n log n)	多重排序，需要保留等值元素的原始顺序
partial_sort	只整理前几本书，其他随便	不稳定（但前m个有序）	O(n log m)	只关心最小的/最大的前m个元素
heap	用堆取极值	–	O(m log n)	灵活的前m个元素，不要求前m个有序时更高效

注：堆（heap）相关的 nth_element 等也是常用排序相关算法，后面会提到。

C++ 完整可运行代码（每行变量带中文注释）

#include <iostream>
#include <vector>
#include <algorithm>   // sort, stable_sort, partial_sort
#include <cstdlib>     // rand
#include <ctime>       // time
using namespace std;

// 自定义比较函数：按数字的个位数升序
bool compareByUnit(int a, int b) {
    return (a % 10) < (b % 10);   // 个位数小的在前
}

// 打印向量的辅助函数
void printVec(const string& msg, const vector<int>& v) {
    cout << msg;
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {
    srand(time(0));   // 初始化随机种子

    // 生成10个0~99的随机数作为原始数据
    vector<int> original;               // 原始数据向量
    for (int i = 0; i < 10; ++i) {
        original.push_back(rand() % 100);   // 随机数 0~99
    }
    printVec("原始数据: ", original);

    // 1. sort 升序（默认）
    vector<int> v1 = original;          // 复制原始数据到v1
    sort(v1.begin(), v1.end());         // 升序排序
    printVec("sort 升序: ", v1);

    // 2. sort 降序（使用 greater<int>()）
    vector<int> v2 = original;          // 复制原始数据到v2
    sort(v2.begin(), v2.end(), greater<int>());  // 降序
    printVec("sort 降序: ", v2);

    // 3. sort 自定义规则（按个位数升序）
    vector<int> v3 = original;          // 复制原始数据到v3
    sort(v3.begin(), v3.end(), compareByUnit);   // 按个位数排序
    printVec("sort 按个位数升序: ", v3);

    // 4. stable_sort 演示稳定性
    // 用 pair 模拟学生（学号, 成绩），先按成绩排，再按学号排（稳定）
    vector<pair<int, int>> students = {{2, 80}, {3, 75}, {2, 75}, {1, 90}};
    // 先按成绩升序（稳定）
    stable_sort(students.begin(), students.end(),
                [](const pair<int,int>& a, const pair<int,int>& b) {
                    return a.second < b.second;   // 成绩小的在前
                });
    // 再按学号升序（稳定，保持成绩相同的顺序）
    stable_sort(students.begin(), students.end(),
                [](const pair<int,int>& a, const pair<int,int>& b) {
                    return a.first < b.first;     // 学号小的在前
                });
    cout << "稳定排序后（学号升序，成绩相同的保持原来顺序）: ";
    for (auto& p : students) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;

    // 5. partial_sort：只排序前3个（最小的3个）
    vector<int> v4 = {5, 7, 2, 9, 1, 4, 3, 8, 6};  // 待排序数据
    cout << "原始数据: ";
    for (int x : v4) cout << x << " ";
    cout << endl;
    partial_sort(v4.begin(), v4.begin() + 3, v4.end());  // 前3个变成最小的且有序
    cout << "partial_sort 前3个后（前3个有序，其余无序）: ";
    for (int x : v4) cout << x << " ";
    cout << endl;

    return 0;
}

运行结果示例（每次随机数不同）：

原始数据: 42 68 35 1 70 25 79 59 63 65 
sort 升序: 1 25 35 42 59 63 65 68 70 79 
sort 降序: 79 70 68 65 63 59 42 35 25 1 
sort 按个位数升序: 70 1 42 63 35 25 65 68 59 79 
稳定排序后（学号升序，成绩相同的保持原来顺序）: (1,90) (2,80) (2,75) (3,75) 
原始数据: 5 7 2 9 1 4 3 8 6 
partial_sort 前3个后（前3个有序，其余无序）: 1 2 3 9 7 4 5 8 6

Python 等价实现（每行变量带中文注释）

import random
import heapq

def print_list(msg, lst):
    """打印列表辅助函数"""
    print(msg, lst)

# 生成10个0~99的随机数作为原始数据
original = [random.randint(0, 99) for _ in range(10)]   # 随机列表
print_list("原始数据: ", original)

# 1. sort 升序（原地排序，Python默认稳定，但这里演示简单排序）
v1 = original.copy()            # 复制原始数据到v1
v1.sort()                       # 升序
print_list("sort 升序: ", v1)

# 2. sort 降序
v2 = original.copy()            # 复制原始数据到v2
v2.sort(reverse=True)           # 降序
print_list("sort 降序: ", v2)

# 3. 自定义规则：按个位数升序
v3 = original.copy()            # 复制原始数据到v3
v3.sort(key=lambda x: x % 10)   # 按个位数排序
print_list("sort 按个位数升序: ", v3)

# 4. 稳定排序：Python的sort本身就是稳定的
data = [(2, 80), (3, 75), (2, 75), (1, 90)]   # (学号, 成绩)
data.sort(key=lambda x: x[1])   # 先按成绩排（稳定）
data.sort(key=lambda x: x[0])   # 再按学号排（稳定，成绩相同的保持原序）
print("稳定排序后（学号升序，成绩相同保持原顺序）:", data)

# 5. 部分排序：使用 heapq.nsmallest（相当于取最小的m个）
v4 = [5, 7, 2, 9, 1, 4, 3, 8, 6]   # 原始数据
print("原始数据:", v4)
# 取最小的前3个，返回有序列表
cheapest_3 = heapq.nsmallest(3, v4)   # 最小的3个元素（有序）
print("最小的前3个:", cheapest_3)

# 如果想模拟 partial_sort 效果（把原列表前3个变成最小的且有序，其余不变）
v5 = v4.copy()                     # 复制原始数据到v5
smallest = heapq.nsmallest(3, v5)  # 最小的3个
v5[:3] = smallest                  # 替换前3个（注意：其余元素保持原顺序，但可能不是最小的）
print("模拟 partial_sort 后 v5:", v5)

运行结果（随机部分变化）：

原始数据: [42, 68, 35, 1, 70, 25, 79, 59, 63, 65]
sort 升序: [1, 25, 35, 42, 59, 63, 65, 68, 70, 79]
sort 降序: [79, 70, 68, 65, 63, 59, 42, 35, 25, 1]
sort 按个位数升序: [70, 1, 42, 63, 35, 25, 65, 68, 59, 79]
稳定排序后（学号升序，成绩相同保持原顺序）: [(1, 90), (2, 80), (2, 75), (3, 75)]
原始数据: [5, 7, 2, 9, 1, 4, 3, 8, 6]
最小的前3个: [1, 2, 3]
模拟 partial_sort 后 v5: [1, 2, 3, 9, 7, 4, 5, 8, 6]

新手容易犯的 5 个错误

以为 sort 是稳定的
很多初学者测试时发现 sort 对简单整数排序看不出来不稳定，于是以为它稳定。实际上对于复杂对象（比如学生），多次排序时相等元素可能互换。需要稳定时一定用 stable_sort。
忘记包含头文件或错误使用容器
C++ 的 sort、stable_sort、partial_sort 都要求随机访问迭代器，所以不能用在 list（链表）上。list 有自己的 sort 成员函数。如果用 list 调用 std::sort，编译会报错。
partial_sort 的参数写错
partial_sort 的三个迭代器是：first, middle, last，表示把 [first, last) 中最小的 (middle-first) 个元素放到 [first, middle) 并有序。很多人把 middle 写错位置，结果排序个数不对。
Python 中混淆 list.sort() 和 sorted()
- list.sort() 原地修改列表，返回 None。
- sorted(lst) 返回新列表，不修改原列表。
  如果写 v = v.sort() 会得到 None，错误！
忽略了 partial_sort 后剩余元素的顺序是未定义的
不要依赖后半部分的内容！如果你需要知道完整排序后的结果，请用 sort。partial_sort 只保证前 m 个是对的，后面的元素可能乱序、也可能部分有序，但标准没有规定。

延伸：再认识一位朋友——`nth_element`

如果你想找一个数组里第 k 小的元素（比如全班中位数是谁），而不关心其他元素的顺序，可以用 nth_element。它比 partial_sort 更快（O(n)），但不保证前k个有序，只保证第 k 个位置上就是第 k 小的元素，并且左边的都不大于它，右边的都不小于它。

vector<int> v = {5, 7, 2, 9, 1, 4, 3, 8, 6};
nth_element(v.begin(), v.begin() + 4, v.end());   // 找第5小的元素（下标4）
// 结果：v[4] 是 5（因为1,2,3,4,5……），左边是 ≤5 的，右边是 ≥5 的

这跟 partial_sort 的区别是：partial_sort 保证前 m 个有序，而 nth_element 不保证有序但更快。在只需要找中位数、成绩第几名等场景时，nth_element 更合适。

总结与相关指引

简单排序：用 sort（C++）或 list.sort() / sorted()（Python）。
多重排序且保持等值顺序：用 stable_sort，比如先按班级再按成绩。
只找前 m 名（不要求全部排序）：用 partial_sort（C++）或 heapq.nsmallest（Python）。
只找第 k 名（不关心顺序）：用 nth_element（C++），Python 可用 heapq.nsmallest(k, data)[-1] 但效率稍低。

如果想深入学习，可以进一步了解：

排序的自定义比较器（lambda、函数对象、operator< 重载）
排序的稳定性在实际项目中的影响（如数据库查询、游戏排行榜）
其他排序算法：归并排序、堆排序、计数排序等，了解它们的适用场景
使用 sort 对结构体/类排序时，如何定义比较规则

掌握了这三个排序工具，你就能轻松应对绝大多数排序问题，就像整理书架一样随心所欲。快去试试吧！

排序算法：sort、stable_sort与partial_sort