Go sort.Interface 怎样稳定排序重复键

已有 sort.Interface 实现时，调用 sort.Stable(data)；直接排序切片时，用 sort.SliceStable。比较器只判断严格先后，例如整数优先级升序用 ，不要用 。相同键的两条记录应在正反比较中都返回 false，稳定排序才会保留它们进入本次排序时的相对次序。

相关 API 契约见 Go 官方文档 https://pkg.go.dev/sort 的 Interface、Stable 与 SliceStable 小节。下面用一个待展示条目列表说明：要保护的是“同优先级记录原有次序”，不是权限、公平性或业务安全的全部保证。

明确需要保护的同键相对次序

假设输入记录依次为 A(2)、B(1)、C(2)、D(1)、E(2)，括号内是 Priority。按优先级升序时，期望 ID 次序为 B、D、A、C、E。这是规则推导出的示例期望，不是本文执行程序取得的输出。

这里有两类资产：记录内容不能在交换中被拆散；同键记录的输入次序不能被无意改写。Priority 为 1 的组内部，B 应保持在 D 前；Priority 为 2 的组内部，A、C、E 的相对关系应保持。ID 不作为次级排序键，否则“相同 Priority”就未必是比较器眼里的等价元素。

稳定只相对于本次输入成立。如果输入来自无序 map 遍历或没有确定次序的上游查询，每次输入本身可能不同，稳定排序不会凭空创造跨请求一致的次序。若业务要求跨次确定的顺序，应先明确额外业务键；这与保留输入次序是两个不同目标。

找出比较器破坏稳定性的入口

风险入口通常不是有人攻击排序器，而是比较规则混入了不受控制的条件。把 Priority 的比较写成小于等于，会把相同记录也判定为“在自己前面”；相同键时返回 i

这些写法都会破坏排序契约，不能靠改用 Stable 补救。例子选择整数键，避免引入浮点 NaN 的额外规则；实际处理浮点字段时，不能未经定义就沿用这一比较器。

区分不稳定排序与无效比较器

用 sort.Sort 或 sort.Slice，风险是同键相对次序没有保证；某个小样本恰好没变化，并不能建立保证。换成稳定入口可以解决这一类问题。用错误的 Less，则是规则本身失效，属于优先处理项：先消除矛盾比较，再选择算法。

还有一种容易误判的情况：先比较 Priority，再比较 ID。它可能是合法规则，但不同 ID 的同 Priority 记录不再等价，所以稳定算法不负责保留这些记录的输入顺序。评审时应问“哪些元素被认为相等”，不能只看函数名有没有 Stable。

实现Stable和SliceStable的同一规则

将下列内容保存为现有 Go 模块中的 ordering.go。两个函数是替代入口，实际业务选择一个即可，不要为了保险对同一份数据连续排序两次。Swap 交换完整 Entry，避免 ID 和 Priority 错配；两种入口都在原切片上重排。

package ordering

import "sort"

// Entry 的 ID 只标识记录，不参与本例排序。
type Entry struct {
    ID string
    Priority int
}

// ByPriority 在原切片上交换整条记录。
type ByPriority []Entry
func (x ByPriority) Len() int { return len(x) }
func (x ByPriority) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
func (x ByPriority) Less(i, j int) bool {
    // 相同优先级时，正反比较都返回 false。
    return x[i].Priority 

对整数键而言，这个规则保持自比较为 false，也不会同时声称 a 在 b 前且 b 在 a 前；小于关系具备传递性。同键相对次序由稳定算法维持，不需要额外保存当前位置。

如果需要降序，将两处优先级比较同时改为 >，相同键仍应返回 false。不要把升序比较简单取反，否则等值情况也会变成 true。调用期间由当前逻辑独占这份可写切片，避免其他 goroutine 修改记录或排序键。

保留可解释的排序约定

排序规则变化可以记录为一条简短的工程决策：字段为 Priority，方向为升序，等价条件为 Priority 相同，同键策略为保留本次输入次序，输入来源由调用方明确。这比只写“修复排序不稳定”更容易审阅，也能判断新增 ID 次级键是不是有意改变产品行为。

这里不要求把完整业务记录写入日志。记录规则版本和输入来源即可用于变更追溯，避免为解释排序而扩散敏感字段。Stable 不会授予任何权限，也不能替代上游对优先级字段的业务约束。

用重复键样本核对契约

将以下用例保存为同包 ordering_test.go。第一组交错输入检查两类同键组，第二组让所有键相同且 ID 故意不按字母排列，防止意外引入 ID 次级键；空输入检查入口可接受空集合。本文未执行测试，读者可在自己的模块中运行。

package ordering

import "testing"

// 两条入口都应满足同键保序，以下用例供读者执行。
func TestStablePriority(t *testing.T) {
    cases := []struct {
        name string
        input []Entry
        want []string
    }{
        {"mixed", []Entry{{"A", 2}, {"B", 1}, {"C", 2}, {"D", 1}, {"E", 2}},
            []string{"B", "D", "A", "C", "E"}},
        {"same", []Entry{{"Z", 3}, {"A", 3}, {"M", 3}},
            []string{"Z", "A", "M"}},
        {"empty", nil, nil},
    }
    sorters := []struct {
        name string
        run func([]Entry)
    }{
        {"interface", StableByInterface},
        {"slice", StableBySlice},
    }
    for _, sorter := range sorters {
        for _, tc := range cases {
            t.Run(sorter.name+"/"+tc.name, func(t *testing.T) {
                // 复制样本，避免一条入口改变另一条入口的输入次序。
                rows := append([]Entry(nil), tc.input...)
                sorter.run(rows)
                if len(rows) != len(tc.want) { t.Fatal("记录数量变化") }
                for i := range rows {
                    if rows[i].ID != tc.want[i] {
                        t.Fatalf("位置 %d: 得到 %s，期望 %s", i, rows[i].ID, tc.want[i])
                    }
                    if i > 0 && rows[i-1].Priority > rows[i].Priority {
                        t.Fatal("优先级不是升序")
                    }
                }
            })
        }
    }
}

# 在放置上述两个文件的模块包目录执行读者自测。
go test -run '^TestStablePriority$' -count=1 .

这些用例用于回归具体契约，不证明任意比较器都正确。新增排序字段后，应补充对应的等价样本；有序性检查也不能替代同键保序检查，因为两个相同键交换后依然可能“有序”。

重复键要不要先去重？

不需要。稳定排序保留记录数量，排序和去重是不同操作。本文没有删除任何 Entry。

已经实现了 Len、Less、Swap，为什么仍会乱序？

这只说明实现了接口。还要检查使用的入口是否稳定，以及 Less 是否把本应等价的记录判为严格先后。

能否给每条记录补原始下标作为次级键？

可以在入参快照中保存不可变的原始序号，但不要使用交换后的位置 i、j。本文直接用稳定入口，不额外维护序号，避免把“当前下标”和“输入序号”混为一谈。

最后保留三个判断：用严格比较表达业务键，用 Stable 或 SliceStable 表达保序要求，用明确的输入来源解释稳定保证的起点。三者缺少任何一项，都不应把偶然出现的顺序当作可靠契约。