排序与自定义排序

排序是每个标准库的标配，但"自定义排序"的实现方式暴露了各语言对"顺序"建模的根本差异。同样是"按年龄排序"，Python 让你提取键，C++ 让你比较两个元素，Go 甚至让你比较两个下标。理解了范式差异，跨语言排序就不必死记 API。

两种排序范式

自定义排序的核心问题是：如何告诉排序算法"谁该排在前面"。主流语言给出两种答案。

比较器范式（comparator）

提供一个比较两个元素的函数，排序算法反复调用它来决定顺序。按返回值约定又分两派：

约定	返回类型	语义	代表语言
布尔小于	`bool`	`true` 表示 a 应在 b 前	C++、Go
三路比较	`int` / `Ordering`	负/零/正	Java、Rust

布尔小于：只回答"a 是否小于 b"，等价关系由 !(a<b) && !(b<a) 隐式推导。
三路比较：一次给出小于/等于/大于三种状态，信息更完整，天然支持链式比较（先比 A，相等再比 B）。

键提取范式（key extraction）

提供一个从元素中提取可比较键的函数，排序算法对每个元素调用一次，得到键后按键排序。等价于 Schwartzian 变换（装饰-排序-去装饰）：先算出每个元素的键，排序，再丢弃键。

Python 是键提取范式的坚定拥护者：key 参数是首选，老式 cmp 比较器在 Python 3 中已移除，需用 functools.cmp_to_key 转换。Java 的 Comparator.comparing、Rust 的 sort_by_key、C++20 的投影（projection）也提供键提取，但不是唯一手段。

两种范式的取舍：键提取只需对每个元素调用一次提取函数（O(n) 次），比较器则在每次比较时调用（O(n log n) 次）。当提取代价高时，键提取显著更快。

稳定性

稳定性指相等元素是否保持原有相对顺序。并非所有内置排序都稳定：

语言	默认排序	稳定？	不稳定替代
C++	`std::sort`	否（IntroSort）	—
C++	`std::stable_sort`	是（归并排序）	`std::sort`
Java	`Arrays.sort(对象)`	是（TimSort）	—
Java	`Arrays.sort(基本类型)`	否（双轴快排）	—
Python	`sorted` / `list.sort`	是（TimSort）	—
Go	`sort.Sort` / `sort.Slice`	否（pdqsort）	`sort.Stable`
Rust	`sort` / `sort_by`	是（归并变种）	`sort_unstable`

不稳定排序通常更快、内存更省。基本类型无所谓稳定性（值相等即完全相同），故 Java 对基本类型选用不稳定算法是合理的。

C++

<algorithm> 提供 std::sort，基于 IntroSort（快排 + 堆排 + 插入排），不稳定，O(n log n)。

#include <algorithm>
#include <vector>

std::vector<int> v{4, 2, 5, 3, 1};
std::sort(v.begin(), v.end());          // 升序
std::sort(v.begin(), v.end(),
          std::greater<int>());         // 降序

比较器返回 bool，true 表示 a 应在 b 前：

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people{
    {"Alice", 25}, {"Bob", 20}, {"Charlie", 23}};

// Lambda：按 age 升序
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

// 函数对象（Functor）：可复用、可有状态
struct ByAge {
    bool operator()(const Person& a,
                    const Person& b) const {
        return a.age < b.age;
    }
};
std::sort(people.begin(), people.end(), ByAge{});

C++20 范围算法支持投影，实现键提取：

#include <algorithm>
#include <ranges>

// 投影：按 age 排序，无需手写比较器
std::ranges::sort(people, {}, &Person::age);
// 第二参数 {} 为默认比较（<），第三参数为投影

C++20 之前若要键提取，需手写 [](auto& a, auto& b) { return a.age < b.age; }；投影让"按某成员排序"一行搞定。

Java

Arrays.sort 排数组，Collections.sort / List.sort 排集合。对象排序用 TimSort（稳定），基本类型用双轴快排（不稳定）。

比较器是 Comparator<T> 函数式接口，核心方法 int compare(T a, T b)：负数 a 在前，零相等，正数 a 在后。

import java.util.*;

int[] arr = {4, 2, 5, 3, 1};
Arrays.sort(arr);                        // 升序

List<Integer> list = new ArrayList<>(
    Arrays.asList(4, 2, 5, 3, 1));
Collections.sort(list);                  // 升序

Lambda 比较器与键提取：

class Person {
    String name;
    int age;
    String getName() { return name; }
    int getAge() { return age; }
}

List<Person> people = new ArrayList<>();

// 比较器范式：按 age 升序
people.sort((a, b) -> Integer.compare(a.age, b.age));

// 键提取范式：Comparator.comparing
people.sort(Comparator.comparing(Person::getAge));
// 降序
people.sort(Comparator.comparing(Person::getAge)
                      .reversed());
// 链式：先按 age，再按 name
people.sort(Comparator.comparing(Person::getAge)
                      .thenComparing(Person::getName));

避免 a.age - b.age 写法：整数溢出时结果错误。用 Integer.compare(a, b) 或 Comparator.comparingInt。

Python

sorted() 返回新列表，list.sort() 原地修改。底层 TimSort，稳定。推荐 key 键提取，不推荐比较器。

nums = [4, 2, 5, 3, 1]
sorted_nums = sorted(nums)          # 新列表
nums.sort()                         # 原地
sorted(nums, reverse=True)          # 降序

people = [
    {'name': 'Alice', 'age': 25},
    {'name': 'Bob', 'age': 20},
    {'name': 'Charlie', 'age': 23},
]

# 键提取（推荐）
sorted(people, key=lambda x: x['age'])
sorted(people, key=lambda x: x['name'],
       reverse=True)

# 多键：返回 tuple，逐元素比较
sorted(people, key=lambda x: (x['age'], x['name']))

复杂比较逻辑用 cmp_to_key 转换老式比较函数（仅在键提取无法表达时）：

from functools import cmp_to_key

# 年龄升序，年龄相同姓名降序
def cmp(a, b):
    if a['age'] != b['age']:
        return a['age'] - b['age']
    return -1 if a['name'] > b['name'] else 1

sorted(people, key=cmp_to_key(cmp))

多数多键排序用 tuple 键即可：key=lambda x: (x['age'], -x['score']) 可混用升降序。cmp_to_key 是最后手段。

Go

sort 包提供排序。Go 1.19+ 底层用 pdqsort（模式击败快排），不稳定。基本类型有 sort.Ints / sort.Strings 等便捷函数。

Go 的比较器独特之处：比较的是下标（i, j）而非元素值，闭包捕获切片：

import "sort"

type Person struct {
    Name string
    Age  int
}

people := []Person{
    {"Alice", 25}, {"Bob", 20}, {"Charlie", 23},
}

// sort.Slice：传 Less 闭包，按下标比较
sort.Slice(people, func(i, j int) bool {
    return people[i].Age < people[j].Age
})

// 稳定排序
sort.SliceStable(people, func(i, j int) bool {
    return people[i].Name > people[j].Name
})

实现 sort.Interface 适合需要复用排序逻辑的场景：

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool {
    return a[i].Age < a[j].Age
}

sort.Sort(ByAge(people))   // 不稳定
sort.Stable(ByAge(people)) // 稳定

Go 1.21+ 新增泛型函数 slices.SortFunc，比较器签名为 func(a, b T) int（三路比较），比 sort.Slice 的下标闭包更直观。

Rust

可变切片 &mut [T] 和 Vec<T> 自带排序方法。sort / sort_by 稳定（归并变种），sort_unstable / sort_unstable_by 不稳定但更快。

sort_by 接收闭包 Fn(&T, &T) -> Ordering，Ordering 是三路枚举（Less / Equal / Greater）：

#[derive(Debug)]
struct Person {
    name: String,
    age: u32,
}

let mut people = vec![
    Person { name: "Alice".into(), age: 25 },
    Person { name: "Bob".into(), age: 20 },
    Person { name: "Charlie".into(), age: 23 },
];

// 比较 age 升序
people.sort_by(|a, b| a.age.cmp(&b.age));
// 比较 name 降序
people.sort_by(|a, b| b.name.cmp(&a.name));
// 链式：先 age，再 name
people.sort_by(|a, b| {
    a.age.cmp(&b.age)
        .then_with(|| a.name.cmp(&b.name))
});

键提取用 sort_by_key（键类型需 Ord）：

// 升序
people.sort_by_key(|p| p.age);

// 降序：反转比较顺序
people.sort_by(|a, b| b.age.cmp(&a.age));
// 或用 Reverse 包装（键需 Copy + Ord）
use std::cmp::Reverse;
people.sort_by_key(|p| Reverse(p.age));

为类型实现 Ord 后可直接 sort()：

#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
struct Person {
    age: u32,        // 先比较 age
    name: String,    // age 相等再比较 name
}
// 现在可直接 people.sort()

横向对比

自定义排序范式

语言	首选范式	比较器返回值	键提取方式
C++	比较器	`bool`	C++20 投影
Java	比较器 + 键提取	`int`	`Comparator.comparing`
Python	键提取	—（已弃用）	`key` 参数
Go	比较器（按下标）	`bool`	无
Rust	比较器 + 键提取	`Ordering`	`sort_by_key`

链式多键排序

"先按年龄，年龄相同再按姓名"是常见需求：

// C++：嵌套判断
std::sort(v.begin(), v.end(),
    [](const auto& a, const auto& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

1
2
3

// Java：thenComparing 链
people.sort(Comparator.comparing(Person::getAge)
                      .thenComparing(Person::getName));

1 2	`# Python：tuple 键 sorted(people, key=lambda x: (x['age'], x['name']))`

// Go：嵌套判断
sort.Slice(people, func(i, j int) bool {
    if people[i].Age != people[j].Age {
        return people[i].Age < people[j].Age
    }
    return people[i].Name < people[j].Name
})

// Rust：then_with 链
people.sort_by(|a, b| {
    a.age.cmp(&b.age)
        .then_with(|| a.name.cmp(&b.name))
});

总结

语言	默认算法	稳定	自定义排序首选
C++	IntroSort	否	Lambda 比较器；C++20 投影
Java	TimSort（对象）	是	`Comparator.comparing`
Python	TimSort	是	`key` 键提取
Go	pdqsort	否	`sort.Slice` 下标闭包
Rust	归并变种	是	`sort_by` 闭包

排序 API 的差异背后是两种建模思路：

比较器把"顺序判断"交给用户，灵活但每次比较都要调用（C++、Java、Go、Rust）；
键提取把"提取排序依据"交给用户，简洁且提取次数少（Python、Java comparing、Rust sort_by_key、C++20 投影）。

掌握"比较器 vs 键提取"这一范式区分，以及各语言比较器的返回值约定（布尔小于 vs 三路比较），跨语言排序即可举一反三。