C++ 排序算法核心解析与 STL 实战

例题：自定义结构体排序

以'生日排序'为例，当需要按年、月、日多级条件排序，且姓名相同则按 ID 倒序时，必须借助结构体和自定义比较器。

#include<bits/stdc++.h>
using namespace std;

struct stu {
    string name;
    int year, month, day;
    int id;
};

// 自定义比较函数
bool compare(const stu& a, const stu& b) {
    if (a.year != b.year) return a.year < b.year;
    if (a.month != b.month) return a.month < b.month;
    if (a.day != b.day) return a.day < b.day;
    return a.id > b.id; // 完全相同时，ID 大的排前面
}

int main() {
    int n;
    cin >> n;
    vector<stu> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].name >> a[i].year >> a[i].month >> a[i].day;
        a[i].id = i; // 记录输入顺序，用于稳定处理
    }
    
    sort(a.begin(), a.end(), compare);
    
    for(auto t : a) cout << t.name << endl;
    return 0;
}

关键点说明：

• 结构体存储：当数据包含多种类型（如字符串 + 整数）时，结构体是最合适的容器。
• 比较函数返回值：返回 true 表示第一个参数应排在第二个参数之前。注意这里不需要修改原序列，只负责比较。
• 稳定性处理：如果题目要求完全相同的元素保持原有相对顺序，可以在比较函数中增加对原始索引的判断。

归并排序

原理

归并排序采用分治思想：先递归拆分序列，再合并有序子序列。其时间复杂度稳定在 O(n log n)，且是稳定排序。

#include<bits/stdc++.h>
using namespace std;

vector<int> a, temp;

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    
    for (int i = l, k = 0; i <= r; i++, k++) a[i] = temp[k];
}

int main() {
    int n;
    cin >> n;
    a.resize(n); temp.resize(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    merge_sort(0, n - 1);
    for(int x : a) cout << x << " ";
    return 0;
}

实现细节：

• 全局数组：将 a 和 temp 设为全局变量，避免递归过程中频繁传递引用，提升性能。
• 临时空间：temp 用于暂存合并结果，最后再拷回原数组。

计算逆序对数量

逆序对定义为 i < j 且 a[i] > a[j]。在归并排序的合并阶段，如果左半部分的当前元素大于右半部分元素，则左半部分剩余的所有元素都与该右半部分元素构成逆序对。

long long numble = 0;

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else {
            temp[k++] = a[j++];
            numble += (mid - i + 1); // 关键计数逻辑
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int i = l, k = 0; i <= r; i++, k++) a[i] = temp[k];
}

第 k 大/小数与部分排序

nth_element（快速选择）

如果只需要找出第 k 个位置的元素，而不关心其他元素的顺序，nth_element 是最佳选择。它的时间复杂度平均为 O(n)。

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    // 找到第 k 小的位置（下标从 0 开始）
    nth_element(a.begin(), a.begin() + k, a.end());
    cout << a[k] << endl;
    return 0;
}

用法提示：

• nth_element(begin, nth, end)：将第 k 个元素放到 nth 位置，左边小于等于它，右边大于等于它。
• 若题目要求第 k 大，可配合 greater<int>() 比较器使用。

partial_sort（部分排序）

当需要输出前 k 个元素且它们内部有序时，使用 partial_sort。

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    // 将前 m 个元素排序好，其余乱序
    partial_sort(a.begin(), a.begin() + m, a.end());
    
    for(int x : a) cout << x << " ";
    return 0;
}

总结

复杂度对比

以上涵盖了 C++ 中排序的核心知识点。实际开发中，优先调用 STL 函数；遇到特殊约束（如逆序对、内存限制）时，再考虑手写算法。