slices.SortedFunc 处理自定义排序稳定性的实践

slices.SortedFunc 适合把 iter.Seq 收集成新切片并按自定义规则排序，但它不保证稳定。如果比较函数对两条记录返回 0，这两条记录的相对位置可能变化。需要保留输入顺序时应使用 slices.SortedStableFunc；需要跨运行得到完全相同的顺序时，则应在比较函数中加入明确的次级键。

这是我在订单列表中踩过的坑：主键只比较优先级，测试数据看起来一直正确，一换成来自 map 的迭代器，同优先级订单就开始“随机跳动”。问题不在迭代器，也不在泛型，而是我把“稳定排序”和“确定性排序”当成了同一件事。

官方文档：https://pkg.go.dev/slices

SortedFunc 为什么会打乱同分记录

Go 1.23 为 slices 增加了基于迭代器的 Sorted、SortedFunc 和 SortedStableFunc。SortedFunc 会先收集序列，再使用比较函数排序，最后返回新切片。空序列返回 nil。

下面的比较器只比较 Priority。两个订单优先级相同时返回 0，因此它们属于同一个等价类；SortedFunc 没有承诺保留类内原顺序。

package main

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

type Order struct {
    ID       string
    Priority int
}

func main() {
    orders := []Order{
        {ID: "A", Priority: 2},
        {ID: "B", Priority: 1},
        {ID: "C", Priority: 1},
    }

    // 只比较优先级；B 与 C 会被比较器视为相等
    sorted := slices.SortedFunc(slices.Values(orders), func(a, b Order) int {
        return cmp.Compare(a.Priority, b.Priority)
    })

    // SortedFunc 返回新切片，不会原地改写 orders
    fmt.Println(sorted)
}

常见误区是“这次输出刚好没变，所以它就是稳定的”。稳定性是 API 契约，不是一次运行的观察结果。即使当前实现碰巧保持了顺序，也不能依赖未承诺的行为。

稳定排序只保留输入顺序

如果产品要求同优先级订单沿用它们进入序列的顺序，直接换成 SortedStableFunc：

// 比较器返回 0 时，稳定排序保留元素在输入序列中的相对位置
sorted := slices.SortedStableFunc(slices.Values(orders), func(a, b Order) int {
    return cmp.Compare(a.Priority, b.Priority)
})

这里的保证很精确：只有比较器判定相等的元素才保留输入相对顺序。它不会自动按创建时间、ID 或数据库主键排序，也不会修复本来就不稳定的输入源。

需要固定结果时加入次级键

如果排序结果会进入分页、缓存键、快照测试或 API 响应，我通常不依赖输入顺序，而是给平局记录一个可解释的次级键。Go 的 cmp.Or 可以按顺序返回第一个非零比较结果：

package ranking

import (
    "cmp"
    "slices"
    "time"
)

type Order struct {
    ID        string
    Priority  int
    CreatedAt time.Time
}

func SortedOrders(seq func(func(Order) bool)) []Order {
    // 主键优先级降序，次级键创建时间升序，最后用唯一 ID 收口
    return slices.SortedFunc(seq, func(a, b Order) int {
        return cmp.Or(
            cmp.Compare(b.Priority, a.Priority),
            a.CreatedAt.Compare(b.CreatedAt),
            cmp.Compare(a.ID, b.ID),
        )
    })
}

加入唯一 ID 后，不同记录几乎不会再返回 0，排序结果不再依赖输入次序。这时使用 SortedFunc 就足够；改成稳定版也不会带来额外语义。

要注意“稳定”和“多字段排序”服务不同需求：

• 同分记录必须按进入队列的先后展示：使用稳定排序。
• 同分记录必须按创建时间和 ID 固定展示：使用显式次级键。
• 先按一个规则稳定排序，再按另一个规则稳定排序：后一次排序是主键，前一次排序留下的顺序是次键。

比较函数要满足严格弱序

SortedFunc 要求比较函数满足严格弱序：a 小于 b 返回负数，a 大于 b 返回正数，相等或不可比较返回 0。比较结果必须自洽，否则排序结果没有可靠含义。

不要用整数相减代替比较，尤其当字段可能接近类型边界时：

// 错误示例：相减可能溢出，破坏比较器的一致性
bad := func(a, b Order) int {
    return a.Priority - b.Priority
}

// 正确示例：cmp.Compare 明确返回 -1、0 或 +1
good := func(a, b Order) int {
    return cmp.Compare(a.Priority, b.Priority)
}

_, _ = bad, good // 示例中保留两个比较器供对照

浮点字段还要考虑 NaN。cmp.Compare 对浮点数给出一致规则：NaN 小于非 NaN，两个 NaN 视为相等，负零与正零相等。直接使用 和 == 拼比较器，很容易让 NaN 破坏传递性。

上游是 map 时稳定排序也救不了

map 的迭代顺序没有保证。如果序列来自 maps.Values(m)，即使使用 SortedStableFunc，同键元素也只是保留“本次 map 迭代”产生的顺序，跨运行仍可能不同。

我会在两种方案中选一个：

1. 比较器加入唯一且稳定的次级键，例如 ID。
2. 先把 map 键收集并排序，再按有序键生成值序列。

package ranking

import (
    "cmp"
    "maps"
    "slices"
)

func SortedMapValues[V any](items map[string]V) []V {
    // 先固定 map 键顺序，避免稳定排序继承随机输入顺序
    keys := slices.Sorted(maps.Keys(items))
    values := make([]V, 0, len(keys))
    for _, key := range keys {
        values = append(values, items[key])
    }
    return values
}

var _ = cmp.Compare[int] // 保留 cmp 导入，提示后续可组合业务比较器

如果后续仍要按业务字段排序，通常更简单的做法是直接把 map 的唯一键放进元素结构，并作为比较器最后一个次级键。

用测试固定排序契约

排序测试不应只断言“主键是递增的”，还要验证平局规则。下面同时固定稳定性和输入不被修改这两个契约：

package ranking_test

import (
    "cmp"
    "slices"
    "testing"
)

type item struct {
    ID    string
    Score int
}

func TestSortedStableFuncKeepsTieOrder(t *testing.T) {
    input := []item{{"A", 2}, {"B", 1}, {"C", 1}}

    // B 与 C 同分，稳定排序必须保留 B 在 C 前面
    got := slices.SortedStableFunc(slices.Values(input), func(a, b item) int {
        return cmp.Compare(a.Score, b.Score)
    })
    want := []item{{"B", 1}, {"C", 1}, {"A", 2}}

    if !slices.Equal(got, want) {
        t.Fatalf("got %v, want %v", got, want)
    }
    if input[0].ID != "A" {
        t.Fatalf("input was modified: %v", input)
    }
}

相关问题

SortedFunc 会修改原切片吗？

它接收 iter.Seq，先收集到新切片再排序，因此不会像 slices.SortFunc 那样原地修改传入切片。

比较函数返回 0 就一定要用稳定排序吗？

不一定。如果平局记录的相对顺序没有业务意义，SortedFunc 就可以；如果结果需要可重复，优先加入明确次级键。

SortedStableFunc 能让 map 值跨运行保持一致吗？

不能。它只能保留当前输入序列的顺序，而 map 迭代顺序本身没有保证。应先固定输入或加入唯一键。

最终可以用一句话判断：保留“进入序列的先后”就用 SortedStableFunc，定义“业务上的最终先后”就补齐比较器的次级键。不要让一次看似稳定的输出替代 API 契约。