排序与自定义排序

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

两种排序范式

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

比较器范式（comparator）

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

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

• 布尔小于：只回答"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	slices.Sort / slices.SortFunc	否（pdqsort）	—
Go	slices.SortStableFunc	是	slices.SortFunc
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);                  // 升序

int[] 自定义排序：Java 标准库没有 Arrays.sort(int[], Comparator) 重载，不能直接给基本类型数组传 Lambda。可以先装箱为 Integer[]，用比较器排序，再写回原 int[]。下面以降序为例：

int[] nums = {4, 2, 5, 3, 1};
Integer[] boxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);

// 自定义比较器：降序；升序则用 Integer.compare(a, b)
Arrays.sort(boxed, (a, b) -> Integer.compare(b, a));

// 拆箱并写回，保留原 int[] 对象
for (int i = 0; i < nums.length; i++) {
  nums[i] = boxed[i];
}
System.out.println(Arrays.toString(nums)); // [5, 4, 3, 2, 1]

此方案需要额外的对象数组，并有装箱、拆箱开销；若要求直接在 int[] 上使用自定义比较器且不装箱，需要自行实现排序或使用支持基本类型比较器的第三方库。仅按数值升序时，直接用 Arrays.sort(nums)。

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

首选：slices 泛型排序（Go 1.21+）

Go 1.21 将 slices 和 cmp 纳入标准库。对切片排序优先用 slices：类型在编译期检查，自定义比较器直接接收元素值，不再依赖下标闭包或手写 sort.Interface。

API	用途	稳定？
slices.Sort(x)	有序类型升序，如整数、浮点数、字符串	否
slices.SortFunc(x, cmp)	自定义三路比较器排序	否
slices.SortStableFunc(x, cmp)	自定义三路比较器稳定排序	是

这三个函数都原地修改切片，不返回新切片。Sort / SortFunc 使用 pdqsort；需要保持比较器判定为相等的元素的原有顺序时，用 SortStableFunc。浮点数用 slices.Sort 排序时，NaN 排在其他值之前。

import (
  "cmp"
  "slices"
)

nums := []int{4, 2, 5, 3, 1}
slices.Sort(nums) // 升序：[1 2 3 4 5]
slices.SortFunc(nums, func(a, b int) int {
  return cmp.Compare(b, a) // 交换参数实现降序
})

type Person struct {
  Name string
  Age  int
}

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

// 按年龄升序；同龄者的相对顺序不保证
slices.SortFunc(people, func(a, b Person) int {
  return cmp.Compare(a.Age, b.Age)
})

// 稳定排序：保留本次调用前同龄者的相对顺序
slices.SortStableFunc(people, func(a, b Person) int {
  return cmp.Compare(a.Age, b.Age)
})

比较器签名为 func(a, b T) int：负数表示 a 在前，零表示排序意义上相等，正数表示 a 在后，并且必须满足严格弱序。不要用 a.Age - b.Age 代替 cmp.Compare，整数溢出可能破坏顺序；浮点数也应使用 cmp.Compare 统一处理 NaN。Go 没有内置的 key 排序参数，在比较器里访问字段仍会在每次比较时重复取键。

返回新切片：Sorted*（Go 1.23+）

Go 1.23 新增面向迭代器的 slices.Sorted、SortedFunc、SortedStableFunc，分别对应上面的三种排序。它们接收 iter.Seq[T]，先收集到新切片，再排序并返回；不是直接接收 []T。已有切片可用 slices.Values 转成迭代器，源切片的元素顺序不变。

nums := []int{4, 2, 5, 3, 1}
sorted := slices.Sorted(slices.Values(nums))
// sorted 为 [1 2 3 4 5]，nums 仍为 [4 2 5 3 1]

descending := slices.SortedFunc(
  slices.Values(nums), func(a, b int) int {
    return cmp.Compare(b, a)
  })

stablePeople := slices.SortedStableFunc(
  slices.Values(people), func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
  })

若不使用迭代器，也可先 slices.Clone(x)，再调用 Sort*。两种方式都是浅拷贝：结构体里的指针、切片等引用仍共享所指数据。稳定性按输入迭代器产出的顺序定义，不会让无序的 map 遍历自动变成确定顺序。

传统 API：sort 包

旧代码中的 sort.Ints / sort.Strings、sort.Slice / sort.SliceStable 仍可用。与 slices.SortFunc 不同，sort.Slice 的比较器返回 bool，比较的是下标（i, j）而非元素值，需通过闭包访问切片：

import "sort"

// 按年龄升序
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，或需要自定义 Len / Swap 行为时，可以继续使用 sort.Sort / sort.Stable；仅为了排序普通切片，无需再定义包装类型：

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)) // 稳定

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	比较器（slices 按元素；sort 按下标）	int / bool	无内置 key 参数
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;
    });

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

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

// Go：三路比较，先 age，再 name
slices.SortFunc(people, func(a, b Person) int {
  if n := cmp.Compare(a.Age, b.Age); n != 0 {
    return n
  }
  return cmp.Compare(a.Name, b.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	否	slices.SortFunc 三路比较器
Rust	归并变种	是	sort_by 闭包

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

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

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