C++ 排序：std::sort、自定义比较器与稳定排序

排序只是另一种算法

在上一页中你看到，标准库提供了现成的算法，它们通过迭代器作用于任何范围。排序是你最常用的那个，它之所以单独占一页，是因为它有几个容易伤人的地方：自定义顺序、稳定性，还有一条规则，一旦违反，你得到的不是错误答案，而是未定义行为。

主力是 <algorithm> 中的 std::sort。你把一个范围的开头和结尾交给它，它就会把元素原地排成升序：

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // ascending, in place

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

这里不会产生拷贝，重新排列的是 vector 本身。std::sort 底层通常是内省排序（会退回堆排序的快速排序），平均复杂度为 O(n log n)。这几乎总是比你自己写排序更快，也不容易出错得多。

它对普通的 C 数组同样适用，只需用指针描述范围：

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // or sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

用比较器自定义顺序

默认情况下，std::sort 用 operator< 给元素排序。想换一种排法，就传入第三个参数：一个比较器，它接收两个元素，如果第一个应该排在第二个之前就返回 true。

lambda 最适合做这件事。降序就是 a > b：

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a before b" when a is larger -> descending
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

对于内置类型的普通降序这种常见情况，标准库甚至提供了现成的比较器，即 <functional> 中的 greater<T>()：

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // same as a > b

比较器也是按值本身以外的东西排序的方法，例如按长度而不是按字母顺序给字符串排序：

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

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // shorter words first
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

对于比几个字节大的东西（比如 string），比较器的参数要用 const& 接收：每次比较都拷贝每个元素纯属浪费。

按字段给结构体排序

在实际程序中，你通常会按某个字段给一组结构体排序。比较器只需取出你关心的字段。这里我们按年龄给人排序，年龄小的在前：

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

注意 Linus 和 Dennis 的年龄都是 25。这里他们恰好保持了原来的相对顺序，但 std::sort 不保证这一点。如果相等元素的相对顺序很重要，就用 std::stable_sort，它会保持这个顺序（性能上略有代价）：

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus stays before Dennis - their input order is preserved
    return 0;
}

要有意地处理并列情况，比如先按年龄、再按名字的字母顺序排序，就只在主键相等时才比较次键。std::tie 让这件事写得很干净：

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // age, then name
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis & Linus 25, alphabetical
    return 0;
}

严格弱序陷阱

这是 C++ 排序中最危险的错误，因为它给你的不是错误答案，而是未定义行为，往往意味着崩溃或越界读取。

std::sort 要求你的比较器定义一个严格弱序。实用的规则是：对任何元素 x，comp(x, x) 必须为 false。换句话说，一个元素永远不会排在它自己“之前”。< 和 > 恰好满足这一点，而 <= 和 >= 恰好破坏了它：

// BUG: returns true when a == b, violating strict weak ordering.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // undefined behavior - may crash on some inputs
});

用 <= 时，比较器声称一个 5 排在另一个 5 之前，这自相矛盾。std::sort 随后可能让指针越过范围的末尾。很小的输入有时看起来没问题，这正是这个 bug 可怕的地方：它可能通过你的测试，却在生产环境中崩溃。修复方法很简单，用 <：

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // correct: false when equal
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

第二个经典陷阱：排序会让所有指向该范围内部的东西失效。 排序前保存的迭代器、指针和下标，排序后不再指向同一个逻辑元素，因为元素已经移动了。需要的任何位置都要在排序之后重新求出，绝不能在之前。

只排序范围的一部分

有时你并不需要全部排好序，只想要前几名。为了读前三个而把整个 vector 排序是一种浪费。std::partial_sort 只排好你要求的那些元素，其余元素的顺序不做保证，所以开销更小：

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Put the 3 smallest, in order, at the front. Rest is unspecified.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

如果你只需要本应位于某个位置上的那一个元素，比如中位数，std::nth_element 做的工作更少：它把正确的元素放到那个下标上，比它小的都在前面，比它大的都在后面，平均只需 O(n)。

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

当“完全有序”超出了问题的实际需要时，就用它们：在大数据上能省下实实在在的时间。

下一节：模板

你有没有注意到，同一个 std::sort 既能处理 int，也能处理 string 和你自己的 Person 结构体，而 greater<int>() 也完全可以写成 greater<string>()？这种通用性不是魔法，而是模板：一种让同一段代码适用于调用者传入的任何类型的机制。下一页我们会学习如何编写自己的模板函数和模板类，让你的代码像你一直在用的这些算法一样与类型无关。