Go Academy · 课时

稳定排序

Q: 「稳定排序」这节课中我会学到什么？

保留相等元素的顺序 你通过在浏览器中直接运行的动手代码来练习 Go Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

保留相等元素的顺序

稳定排序 是 CoddyKit 上的免费 Go Academy 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Go Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Go Academy 课程共包含 4 节课。

什么是稳定排序

稳定排序会保留相等元素原本的相对顺序。如果两条记录的比较结果相等，原本排在前面的记录仍会排在前面。

为何重要

当您按一个字段排序，但希望在出现平局时保留之前的顺序，稳定性就很重要。例如按城市排序，同时保留每个城市中人员的字母顺序。

sort.Slice 不是稳定的

普通的 sort.Slice 不保证稳定性。相等的元素可能会改变顺序。若要保证稳定性，请使用 sort.SliceStable。

sort.SliceStable

sort.SliceStable 与 sort.Slice 具有相同的签名，但会保留相等元素的顺序。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{3, 1, 2, 1}
	sort.SliceStable(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	fmt.Println(nums)
}

通过结构体观察稳定性

按年龄对人员排序。使用稳定排序时，年龄相同的人员会保留其输入顺序。

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func main() {
	p := []Person{{"Ann", 30}, {"Bob", 25}, {"Cara", 30}}
	sort.SliceStable(p, func(i, j int) bool {
		return p[i].Age < p[j].Age
	})
	fmt.Println(p)
}

Ann 排在 Cara 前面

在前面的示例中，Ann 和 Cara 的年龄都是 30。由于 Ann 在输入中先出现，稳定排序会让 Ann 在结果中排在 Cara 前面。

多轮排序

稳定性使分轮排序成为可能。先按最不重要的键排序，再按最重要的键排序。每一轮稳定排序都会在出现平局时保留之前的顺序。

package main

import (
	"fmt"
	"sort"
)

type Rec struct {
	City string
	Name string
}

func main() {
	r := []Rec{{"Rome", "Zoe"}, {"Oslo", "Ann"}, {"Rome", "Ann"}}
	sort.SliceStable(r, func(i, j int) bool { return r[i].Name < r[j].Name })
	sort.SliceStable(r, func(i, j int) bool { return r[i].City < r[j].City })
	fmt.Println(r)
}

sort.Stable

对于实现了 sort.Interface 的类型，请使用 sort.Stable 而不是 sort.Sort，以获得稳定性。

package main

import (
	"fmt"
	"sort"
)

type ByLen []string

func (s ByLen) Len() int           { return len(s) }
func (s ByLen) Less(i, j int) bool { return len(s[i]) < len(s[j]) }
func (s ByLen) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func main() {
	w := []string{"bb", "cc", "a"}
	sort.Stable(ByLen(w))
	fmt.Println(w)
}

稳定性的成本

与不稳定排序相比，稳定排序可能会使用略多的内存或时间。如果不需要保留相等元素的顺序，直接使用 sort.Slice 即可。

何时选择稳定排序

请在以下情况下选择稳定排序：

元素原本的顺序具有意义
您要根据不同的键进行多轮排序
相等的元素不能被打乱顺序

稳定排序检查示例

两个排序键相等的元素在输入中按 A、B 的顺序出现。稳定排序保证输出中 A 仍位于 B 之前。

package main

import (
	"fmt"
	"sort"
)

func main() {
	type T struct{ Key, Tag int }
	ts := []T{{1, 100}, {1, 200}, {0, 300}}
	sort.SliceStable(ts, func(i, j int) bool { return ts[i].Key < ts[j].Key })
	fmt.Println(ts)
}

快速检查

您使用 sort.SliceStable 按城市对记录进行排序。其中两条记录的城市相同。可以保证什么？

回顾

稳定排序会保留相等元素的顺序：

对切片使用 sort.SliceStable
对 sort.Interface 类型使用 sort.Stable
支持根据不同的键进行多轮排序

常见问题解答

「稳定排序」课时是免费的吗？

是的 — 「稳定排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Go Academy 课程的其余内容，请升级到 CoddyKit PRO。 Go Academy 课程共包含 4 节课。

「稳定排序」这节课中我会学到什么？

保留相等元素的顺序你通过在浏览器中直接运行的动手代码来练习 Go Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Go Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Go Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「稳定排序」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Go Academy 课中编写并运行代码吗？

能。每节 Go Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Go Academy