RootStack

C++ 算法技巧 — 排序 (Sorting)

5分钟阅读

章节概述

排序是将无序数据按一定规则排列的算法，是许多高级算法的基础。
C++ STL sort 基于快排+插入排序优化，平均和最坏 O(n log n)。

核心原理

1. STL sort 的底层实现

C++ 标准库 sort 使用内省排序 (Introsort)：混合快速排序、堆排序和插入排序。

  • 大部分情况: 快速排序 O(n log n)
  • 递归过深时: 切换堆排序保证最坏 O(n log n)
  • 小规模时: 切换插入排序减少常数

2. 自定义排序规则

// 降序排序
bool cmp(int a, int b) { return a > b; }
sort(arr, arr + n, cmp);
 
// 结构体多级排序
bool cmp(Stu a, Stu b) {
    if (a.sum != b.sum) return a.sum > b.sum;  // 总分降序
    if (a.ch != b.ch) return a.ch > b.ch;       // 语文降序
    return a.id < b.id;                         // 学号升序
}

3. 排序稳定性

函数稳定性复杂度
sort不稳定O(n log n)
stable_sort稳定O(n log n)
unique只去相邻重复O(n)

4. 关键组合

排序 + 去重: sort → unique → 二分查找（O(n log n) 预处理后 O(log n) 查询）

关键数据结构

P1177 快速排序

题目: 读入 n 个数字并排序后输出。

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

P1059 [NOIP2006 普及组] 明明的随机数

题目: N 个随机整数，要求去重后从小到大排序输出。

#include <iostream>
#include <algorithm>
using namespace std;
int a[1005];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int cnt = unique(a, a + n) - a;
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) cout << a[i] << " ";
    return 0;
}

P1093 [NOIP2007 普及组] 奖学金

题目: N 个学生的语文、数学、英语成绩，按总分降序排列；总分相同按语文降序；语文也相同按学号升序。

#include <iostream>
#include <algorithm>
using namespace std;
 
struct Stu {
    int id, ch, ma, en, sum;
};
 
bool cmp(Stu a, Stu b) {
    if (a.sum != b.sum) return a.sum > b.sum;
    if (a.ch != b.ch) return a.ch > b.ch;
    return a.id < b.id;
}
 
int main() {
    int n;
    Stu s[305];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i].ch >> s[i].ma >> s[i].en;
        s[i].id = i + 1;
        s[i].sum = s[i].ch + s[i].ma + s[i].en;
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < 5 && i < n; i++)
        cout << s[i].id << " " << s[i].sum << endl;
    return 0;
}

P1068 [NOIP2009 普及组] 分数线划定

题目: N 个选手，计划录取人数 m 的 150%（向下取整），按分数降序排序，录取分数线为计划录取的最后一名选手的分数。

#include <iostream>
#include <algorithm>
using namespace std;
 
struct P { int id, score; };
bool cmp(P a, P b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
}
 
int main() {
    int n, m;
    P p[5005];
    cin >> n >> m;
    m = m * 1.5;
    for (int i = 0; i < n; i++)
        cin >> p[i].id >> p[i].score;
    sort(p, p + n, cmp);
    int line = p[m - 1].score;
    int cnt = m;
    while (cnt < n && p[cnt].score == line) cnt++;
    cout << line << " " << cnt << endl;
    for (int i = 0; i < cnt; i++)
        cout << p[i].id << " " << p[i].score << endl;
    return 0;
}

推荐练习题（洛谷）

相关技巧

  • 贪心: 部分背包问题依赖排序预处理
  • 下标技巧: 排序后下标变化与原始位置映射
  • 二分查找: 排序是二分的必要前提
  • 暴力枚举: 排序可将 O(n^2) 枚举优化为 O(n log n)

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |

关系图谱

反向链接