Go sort.SliceStable 保持同键顺序的排序实现

我在整理一批带有“优先级”和“录入顺序”的任务时，遇到过一个看似普通却很容易被忽略的问题：按优先级排完以后，同一优先级的任务还要按照原来的先后处理。这个要求不能只写成“升序排序”，因为普通排序并不承诺同键记录保留相对顺序。

Go 的 sort.SliceStable 正好解决稳定性这一层：它使用闭包提供比较规则，并让比较结果相等的元素保持原顺序。但它仍然会直接改动传入的切片；如果原数据还要用于审计、回放或另一条处理链，就要先复制一份。

记住两个边界：sort.SliceStable 负责“同键保序”，不负责“保留原切片”；比较函数只比较排序键，同键时应当返回 false。

先把“同键顺序变了”变成可观察结果

不要直接用字符串列表做实验，否则看不出两个相同键的记录到底有没有换位。我会给每条记录保留一个输入序号，再用稳定排序键重新输出这个序号。这样结果中的顺序变化就很直观。

package main

import (
    "fmt"
    "sort"
)

type Task struct {
    Name     string
    Priority int
    InputNo  int // 记录进入切片时的位置，用来观察同键是否保序
}

func main() {
    tasks := []Task{
        {Name: "整理日志", Priority: 2, InputNo: 0},
        {Name: "生成报表", Priority: 1, InputNo: 1},
        {Name: "刷新缓存", Priority: 2, InputNo: 2},
        {Name: "发送通知", Priority: 1, InputNo: 3},
    }

    sort.SliceStable(tasks, func(i, j int) bool {
        // 只比较 Priority；相等时不人为追加 InputNo 排序。
        return tasks[i].Priority 

预期观察点不是“所有任务有序”这么宽泛，而是：优先级 1 的输入序号仍为 1、3，优先级 2 的输入序号仍为 0、2。把一个排序规则拆成这个可见指标，后面排查比较函数时会更快。

比较函数只回答“谁应该排在前面”

sort.SliceStable 的第二个参数是 func(i, j int) bool。返回值表达的是“第 i 个元素是否应该排在第 j 个元素之前”，而不是“两个元素是否相等”。因此只按优先级升序时，比较函数应该写成 tasks[i].Priority 。

当两个优先级相同，tasks[i].Priority 和反方向判断都会是 false。稳定排序会把这理解为同键，保留二者在输入切片中的相对顺序。不要为了“让结果更确定”偷偷把 InputNo 加成第二排序键：一旦加上它，你表达的就变成了复合排序，而不是观察稳定性。

lessByPriority := func(i, j int) bool {
    // 只声明业务键；同键记录交给稳定排序保留原顺序。
    return tasks[i].Priority 

如果业务确实要求“优先级相同再按名称”，可以显式写第二键；这时名称相同的记录仍能从稳定性中获益，但名称不同的记录会按第二键重新排列。

sort.SliceStable(tasks, func(i, j int) bool {
    // 先比较优先级，再按名称；第二键是业务要求，不是稳定性的替代品。
    if tasks[i].Priority != tasks[j].Priority {
        return tasks[i].Priority 

原地排序和排序副本是两个不同决定

稳定只描述同键元素的相对顺序，不会复制底层数组。调用后，tasks 本身已经按新顺序排列；如果后面还要按照原录入顺序写审计日志，就先分配一个同长度切片，再用 copy 复制元素。

original := []Task{
    {Name: "整理日志", Priority: 2, InputNo: 0},
    {Name: "生成报表", Priority: 1, InputNo: 1},
    {Name: "刷新缓存", Priority: 2, InputNo: 2},
    {Name: "发送通知", Priority: 1, InputNo: 3},
}

sorted := make([]Task, len(original))
copy(sorted, original) // 复制结构体元素，避免排序改写 original 的元素顺序

sort.SliceStable(sorted, func(i, j int) bool {
    // 只改变 sorted 的排列，不影响 original 的遍历顺序。
    return sorted[i].Priority 

这里的 Task 是值类型，copy 会复制每个结构体值。如果结构体字段里还有指针、切片或 map，复制的是引用，排序副本只保证“外层切片顺序”独立，不等于所有嵌套数据都深拷贝。

遇到结果不对时，按三层线索排查

1. 先看比较键。确认闭包引用的是当前待排序的切片，并且排序期间没有在外部修改它。
2. 再看同键定义。如果比较函数加入了时间、名称或输入序号，同键范围会变窄，结果变化可能是复合键带来的，而不是稳定排序失效。
3. 最后看副本边界。如果原切片顺序也改变了，通常不是稳定性问题，而是直接把原切片传给了排序函数；应在调用前复制。

还要避免让比较函数返回不一致的结果。例如比较浮点字段时，如果业务允许 NaN，就应该先定义 NaN 的排序策略；比较函数必须形成稳定、可重复的排序关系，否则换什么排序函数都可能出现难以解释的结果。

什么时候换成泛型排序函数

如果项目已经使用较新的 Go 版本，标准库 slices 包提供了泛型的 SortStableFunc，可以把“按索引取元素”的闭包改成直接比较两个值。旧代码或只想最小改动时，sort.SliceStable 仍然清晰；新代码则可以根据项目最低 Go 版本和团队习惯选择。

import "slices"

type Result struct {
    Score int
    Seq   int
}

results := []Result{{Score: 8, Seq: 0}, {Score: 6, Seq: 1}, {Score: 8, Seq: 2}}
slices.SortStableFunc(results, func(a, b Result) int {
    // 返回负数表示 a 在前，零表示同键，正数表示 b 在前。
    switch {
    case a.Score  b.Score:
        return 1
    default:
        return 0
    }
})

无论使用哪种 API，都要单独决定两件事：同键记录是否要保留输入顺序，以及是否允许修改调用方持有的切片。把这两个问题写进测试名称或函数注释，后续维护时就不会把“稳定”误解成“不可变”。

最后用一个小检查表收束实现

相关问题

sort.Slice 和 sort.SliceStable 的主要区别是什么？前者不保证比较相等元素的相对顺序，后者会保持这种相对顺序。

sort.SliceStable 会返回一个新切片吗？不会，它对传入的切片原地排序；需要副本时要自己复制。

同键时能不能返回 true？不应该。比较函数应表达严格的“排在前面”，同键通常让正反方向都返回 false。

copy 后修改结构体里的 map 会影响原数据吗？会，copy 只复制外层元素值；如果还要隔离嵌套引用，需要按数据模型另做深复制。