# 排序：多级键与稳定性

学习目标：掌握自定义比较器、复合多级键排序（主键与次级键）以及稳定排序（Stable Sort）在各语言中的实现。

前置知识与范围：结构体/对象、数组与基本比较。演示在内存中对带时间戳的事件进行多字段排序。

# 问题与边界

给定一组事件记录 Event { timestamp, name }：

待排序列表：
1. (timestamp: 100, name: "b_event")
2. (timestamp: 200, name: "c_event")
3. (timestamp: 100, name: "a_event")
排序规则：
- 一级主键：按时间戳 timestamp 升序排列。
- 二级次键：当时间戳相同时，按名称 name 字典序升序排列。
排序后预期严格顺序：
1. (100, "a_event")
2. (100, "b_event")
3. (200, "c_event")

# 关键差异

语言	默认排序算法稳定性	多级排序键语法	原地 vs 产生新集合
Rust	`sort()` 保证稳定；`sort_unstable()` 速度更快不稳定	`sort_by_key(	e
Go	`slices.SortFunc`（Go 1.21+）或 `sort.SliceStable`	比较函数中 `if cmp != 0 { return cmp } return cmp2`	原地修改切片底层数组
Java	`List.sort()` 采用 TimSort（稳定）	`Comparator.comparing(...).thenComparing(...)`	原地修改可变列表
JavaScript	`Array.prototype.sort()`（ES2019+ 规范要求稳定）	`a.ts - b.ts
TypeScript	沿用 JS `sort()`	多条件短路比较	原地修改
Kotlin	`sortedWith`（稳定）	`compareBy<Event> { it.timestamp }.thenBy { it.name }`	默认返回新排序列表
Python	TimSort（严格稳定）	`list.sort(key=lambda e: (e.timestamp, e.name))`	`sort()` 原地修改；`sorted()` 返回新列表
C++	`std::sort`（不稳定）；`std::stable_sort`（稳定）	比较 lambda 使用 `std::tie` 比较元组	原地修改序列容器

# 各语言实现

# Rust

Rust#[derive(Debug, PartialEq, Eq)]
struct Event<'a> {
    timestamp: i64,
    name: &'a str,
}

fn main() {
    let mut events = [
        Event { timestamp: 100, name: "b_event" },
        Event { timestamp: 200, name: "c_event" },
        Event { timestamp: 100, name: "a_event" },
    ];

    // 利用元组 (timestamp, name) 自然支持多级升序比对
    events.sort_by_key(|e| (e.timestamp, e.name));

    assert_eq!(events[0], Event { timestamp: 100, name: "a_event" });
    assert_eq!(events[1], Event { timestamp: 100, name: "b_event" });
    assert_eq!(events[2], Event { timestamp: 200, name: "c_event" });

    println!("first: {}", events[0].name);
}

Rust 的元组实现了按元素从左至右字典序比对，sort_by_key 配合元组是表达多级排序的最惯用手段。

# Go

Gopackage main

import (
	"cmp"
	"fmt"
	"slices"
)

type Event struct {
	Timestamp int64
	Name      string
}

func main() {
	events := []Event{
		{Timestamp: 100, Name: "b_event"},
		{Timestamp: 200, Name: "c_event"},
		{Timestamp: 100, Name: "a_event"},
	}

	slices.SortStableFunc(events, func(a, b Event) int {
		if c := cmp.Compare(a.Timestamp, b.Timestamp); c != 0 {
			return c
		}
		return cmp.Compare(a.Name, b.Name)
	})

	if events[0].Name != "a_event" || events[1].Name != "b_event" || events[2].Name != "c_event" {
		panic("sort mismatch")
	}

	fmt.Printf("first: %s\n", events[0].Name)
}

Go 1.21 引入泛型包 cmp 与 slices，SortStableFunc 提供严格稳定的比较排序。

# Java

Javaimport java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    public record Event(long timestamp, String name) {}

    public static void main(String[] args) {
        List<Event> events = new ArrayList<>(List.of(
            new Event(100, "b_event"),
            new Event(200, "c_event"),
            new Event(100, "a_event")
        ));

        events.sort(Comparator.comparingLong(Event::timestamp)
                              .thenComparing(Event::name));

        assert "a_event".equals(events.get(0).name());
        assert "b_event".equals(events.get(1).name());
        assert "c_event".equals(events.get(2).name());

        System.out.println("first: " + events.get(0).name());
    }
}

Java 的 Comparator.thenComparing 提供了高度可读的多级比较器链式组合。

# JavaScript

JavaScriptconst assert = {
  equal: (a, b) => { if (a !== b) throw new Error(`${a} !== ${b}`); },
  deepEqual: (a, b) => { if (JSON.stringify(a) !== JSON.stringify(b)) throw new Error(`${JSON.stringify(a)} !== ${JSON.stringify(b)}`); },
  throws: (fn, errType) => {
    try { fn(); throw new Error("expected throw"); } catch (e) {
      if (e.message === "expected throw") throw e;
      if (errType && !(e instanceof errType)) throw e;
    }
  }
};

const events = [
  { timestamp: 100, name: "b_event" },
  { timestamp: 200, name: "c_event" },
  { timestamp: 100, name: "a_event" },
];

events.sort((a, b) => {
  const timeDiff = a.timestamp - b.timestamp;
  if (timeDiff !== 0) return timeDiff;
  return a.name.localeCompare(b.name);
});

assert.equal(events[0].name, "a_event");
assert.equal(events[1].name, "b_event");
assert.equal(events[2].name, "c_event");

console.log(`first: ${events[0].name}`);

ECMAScript 2019 起规范要求 Array.prototype.sort 必须稳定。字符串比较应使用 localeCompare。

# TypeScript

TypeScriptconst assert = {
  equal: (a: unknown, b: unknown) => { if (a !== b) throw new Error(`${a} !== ${b}`); },
  deepEqual: (a: unknown, b: unknown) => { if (JSON.stringify(a) !== JSON.stringify(b)) throw new Error(`${JSON.stringify(a)} !== ${JSON.stringify(b)}`); },
  throws: (fn: () => void, errType?: unknown) => {
    try { fn(); throw new Error("expected throw"); } catch (e: unknown) {
      if (e instanceof Error && e.message === "expected throw") throw e;
      if (typeof errType === "function" && !(e instanceof errType)) throw e;
    }
  }
};

interface Event {
  timestamp: number;
  name: string;
}

const events: Event[] = [
  { timestamp: 100, name: "b_event" },
  { timestamp: 200, name: "c_event" },
  { timestamp: 100, name: "a_event" },
];

events.sort((a, b) => {
  const timeDiff = a.timestamp - b.timestamp;
  if (timeDiff !== 0) return timeDiff;
  return a.name.localeCompare(b.name);
});

assert.equal(events[0].name, "a_event");
assert.equal(events[1].name, "b_event");
assert.equal(events[2].name, "c_event");

console.log(`first: ${events[0].name}`);

TypeScript 严格保证比较器回调参数类型完整。

# Kotlin

Kotlindata class Event(val timestamp: Long, val name: String)

fun main() {
    val events = listOf(
        Event(100, "b_event"),
        Event(200, "c_event"),
        Event(100, "a_event")
    )

    val sorted = events.sortedWith(
        compareBy<Event> { it.timestamp }.thenBy { it.name }
    )

    check(sorted[0].name == "a_event")
    check(sorted[1].name == "b_event")
    check(sorted[2].name == "c_event")

    println("first: ${sorted[0].name}")
}

Kotlin 的 sortedWith 搭配 compareBy 与 thenBy 返回新创建的排序列。

# Python

Pythonfrom typing import NamedTuple, List

class Event(NamedTuple):
    timestamp: int
    name: str

if __name__ == "__main__":
    events = [
        Event(100, "b_event"),
        Event(200, "c_event"),
        Event(100, "a_event"),
    ]

    events.sort(key=lambda e: (e.timestamp, e.name))

    assert events[0].name == "a_event"
    assert events[1].name == "b_event"
    assert events[2].name == "c_event"

    print(f"first: {events[0].name}")

Python 的 key 函数支持返回元组 (e.timestamp, e.name)，利用元组天然的逐项比对实现多级排序。

# C++

C++#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <cassert>

struct Event {
    int64_t timestamp;
    std::string name;
};

int main() {
    std::vector<Event> events = {
        {100, "b_event"},
        {200, "c_event"},
        {100, "a_event"}
    };

    std::stable_sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return std::tie(a.timestamp, a.name) < std::tie(b.timestamp, b.name);
    });

    assert(events[0].name == "a_event");
    assert(events[1].name == "b_event");
    assert(events[2].name == "c_event");

    std::cout << "first: " << events[0].name << "\n";
}

C++ 推荐使用 std::tie 绑定引用元组执行 < 运算，表达复合多级比较；稳定排序需调用 std::stable_sort。

# 迁移误区与适用限制

JS 默认排序陷阱：若直接调用 [10, 2, 5].sort()，JS 会将数字先转为字符串再按 ASCII 排序，得到 [10, 2, 5]。任何非纯字符串数组排序都必须显式传入比较函数！
严格弱序（Strict Weak Ordering）：在 C++ 和 Java 中，比较器必须遵守严格弱序。例如写 a.ts > b.ts 并在相等时返回 true，会导致越界段错误崩溃或 IllegalArgumentException: Comparison method violates its general contract。

# 运行与验证

语言版本基线见示例基线。所有程序运行后控制台输出均为：

纯文本first: a_event

多级复合主次键升序逻辑测试均通过。