FANGT

算法库：排序函数

作者：

fangys

1. std::sort —— 最通用的快速排序

原型：

void sort(RandomIt first, RandomIt last);
void sort(RandomIt first, RandomIt last, Compare comp);

功能：对区间 [first, last) 内的元素进行升序排序（默认使用 < 比较）。平均时间复杂度 O(n log n)，最坏情况通常也是 O(n log n)（内省排序，避免退化）。

特点：

  • 不保证稳定（相等元素的相对顺序可能改变）。
  • 要求随机访问迭代器（vector、array、deque、普通数组等）。
  • 可以自定义比较函数或 lambda。

示例：

#include <algorithm>
#include <vector>
using namespace std;

vector<int> v = {5, 2, 8, 1, 9};
sort(v.begin(), v.end());                     // 升序：1 2 5 8 9
sort(v.begin(), v.end(), greater<int>());     // 降序：9 8 5 2 1

// 自定义比较：按绝对值排序
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});

2. std::stable_sort —— 稳定排序

原型：同 sort。

功能：与 sort 相同，但保证稳定（相等元素的原始顺序不变）。时间复杂度：有足够额外内存时 O(n log n)，否则 O(n log² n)。

适用场景：需要稳定性的排序（如先按成绩排序，同成绩按学号排序时，先用稳定排序按成绩排）。

示例：

struct Student { string name; int score; };
vector<Student> stu = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 90}};
stable_sort(stu.begin(), stu.end(),
    [](const Student& a, const Student& b) { return a.score > b.score; });
// 成绩相同（90分）的同学保持原顺序：Alice 在 Charlie 前

3. std::partial_sort —— 部分排序

原型：

void partial_sort(RandomIt first, RandomIt middle, RandomIt last);
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);

功能：将区间 [first, last) 中最小的 (middle - first) 个元素按升序放到 [first, middle)，剩余元素不保证顺序。

时间复杂度：约 O(n log k)，其中 k = middle – first。

适用场景：只需要前 k 小（或前 k 大）元素，不关心其余顺序。

示例：

vector<int> v = {9, 5, 2, 7, 1, 8};
partial_sort(v.begin(), v.begin() + 3, v.end()); // 前3个最小元素有序
// v 可能变为：1 2 5 9 7 8 （后三个无序）

若要前 k 大，可用 greater<int>() 或自定义比较。

4. std::nth_element —— 快速选择

原型：

void nth_element(RandomIt first, RandomIt nth, RandomIt last);
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

功能：重新排列区间，使得第 nth 个位置的元素是整个区间中第 n 小的元素（按升序）。所有在它之前的元素 ≤ 它，之后的元素 ≥ 它。不保证完全排序。

时间复杂度：平均 O(n)，最坏 O(n²) 但罕见。

适用场景：找中位数、第 k 小/大元素、划分数据（如快速选择）。

示例：

vector<int> v = {5, 2, 8, 1, 9, 3};
nth_element(v.begin(), v.begin() + 2, v.end()); // 第2小（下标2）的元素
// v[2] 的值是第3小的数（下标从0开始），如 v 可能变为 {1,2,3,8,9,5}，v[2]==3
// 左边都 ≤3，右边都 ≥3

// 找中位数
auto mid = v.begin() + v.size()/2;
nth_element(v.begin(), mid, v.end());
cout << "中位数: " << *mid << endl;

辅助函数：std::is_sorted / is_sorted_until

检查区间是否已经有序。

vector<int> v = {1,2,3,4};
if (is_sorted(v.begin(), v.end())) {
    cout << "已排序" << endl;
}
auto it = is_sorted_until(v.begin(), v.end()); // 返回第一个破坏顺序的位置

自定义比较函数

  • 使用内置仿函数：std::greater<int>() 降序，std::less<int>() 升序。
  • 使用 lambda 表达式：
  sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 降序
  • 使用普通函数：
  bool cmp(int a, int b) { return a > b; }
  sort(v.begin(), v.end(), cmp);
  • 对结构体排序：
  struct Node { int x, y; };
  vector<Node> a;
  sort(a.begin(), a.end(), [](const Node& p, const Node& q) {
      if (p.x != q.x) return p.x < q.x;
      return p.y > q.y;
  });

效率对比与竞赛选择

函数时间复杂度稳定性额外空间适用场景
sortO(n log n)不稳定O(log n) 栈通用排序（最快）
stable_sortO(n log n)稳定O(n) 可能需要稳定排序时
partial_sortO(n log k)部分稳定O(k)只需前 k 小
nth_element平均 O(n)不稳定O(1)找第 k 小/中位数

竞赛建议：

  • 默认使用 sort，它是混合排序（内省排序），综合性能最好。
  • 遇到需要稳定排序的情况（如排序后不影响相同元素的原有顺序），用 stable_sort。
  • 只关心最小的 k 个元素时，partial_sort 比完整排序快。
  • 找第 k 小或中位数时，使用 nth_element，千万不要用 sort 后再取第 k 个（浪费时间）。

对普通数组的用法

int arr[] = {5, 2, 8, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);                 // 升序
sort(arr, arr + n, greater<int>()); // 降序

注意事项

  • 比较函数必须提供严格弱序（即满足传递性、反对称性等）。
  • sort 对 vector<bool> 不适用，因为其迭代器不满足要求。
  • 如果排序的对象是自定义类型且没有重载 <，必须提供比较函数或 lambda。

速查表

需求代码示例
升序排序sort(v.begin(), v.end())
降序排序sort(v.begin(), v.end(), greater<int>())
稳定排序stable_sort(v.begin(), v.end())
前5个最小元素partial_sort(v.begin(), v.begin()+5, v.end())
找第3小元素nth_element(v.begin(), v.begin()+2, v.end())
检查是否有序is_sorted(v.begin(), v.end())