Golang 切片排序：slices.Sort、SortFunc 与多字段排序

给内置类型排序

slices.Sort 可以给任何元素类型有序的切片排序：整数、浮点数和字符串。它原地排序，不返回任何值。

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{42, 7, 19, 3, 88}
	slices.Sort(nums)
	fmt.Println(nums)

	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.Sort(names)
	fmt.Println(names) // byte order: uppercase before lowercase

	fmt.Println(slices.IsSorted(nums))

	i, found := slices.BinarySearch(nums, 19)
	fmt.Println(i, found)
}

输出：

[3 7 19 42 88]
[Bob Carl alice lisa]
true
2 true

字符串按字节排序，所以所有大写 ASCII 字母都排在小写字母前面。给名字排序时，这很少是用户想要的结果。下一节会解决这个问题。

slices 包在 Go 1.21 中加入。它的 Sort 是 pattern-defeating quicksort：O(n log n)、原地排序，而且不稳定。

用 SortFunc 自定义顺序

slices.SortFunc 接收一个比较函数 func(a, b T) int。a 应该排在前面时返回负数，b 应该排在前面时返回正数，两者相等时返回零。对有序类型，辅助函数 cmp.Compare 返回的正是这样的值。

package main

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

func main() {
	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.SortFunc(names, func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})
	fmt.Println(names)

	// Descending: swap a and b.
	nums := []int{42, 7, 19, 3, 88}
	slices.SortFunc(nums, func(a, b int) int {
		return cmp.Compare(b, a)
	})
	fmt.Println(nums)

	// By length, shortest first.
	words := []string{"banana", "fig", "apple", "kiwi"}
	slices.SortFunc(words, func(a, b string) int {
		return cmp.Compare(len(a), len(b))
	})
	fmt.Println(words)
}

在比较函数里调用 strings.ToLower，只要输入中有大写字母就会分配一个新字符串，而比较大约要执行 n log n 次。切片很大时，先一次性算好小写形式的键。对其他语言的名字（重音符号、地区规则），用 golang.org/x/text/collate，它不在标准库里。

比较函数必须前后一致：如果它说 a 在 b 前面，就必须也说 b 在 a 后面。违反这一点的函数（例如两个值只要不同就返回 -1）会得到顺序错误的切片，而且不会报任何错。整数相减（return a - b）看起来很简洁，但值很大时会溢出；请用 cmp.Compare。

给结构体排序

比较函数拿到的是元素本身，所以按某个字段给结构体排序也是同一个调用：

package main

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

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	for _, e := range staff {
		fmt.Println(e.Salary, e.Name)
	}
}

这里工资相同的员工可能以任意顺序输出，因为 SortFunc 不是稳定排序。如果需要确定的顺序，要么用更多字段打破平局，要么用稳定排序。

按多个字段排序

先比较最重要的字段，只有平局时才比较下一个。cmp.Or（Go 1.22）返回它的第一个非零参数，这样一行就能写完：

package main

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

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	// Department A to Z, then salary high to low, then name A to Z.
	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Or(
			cmp.Compare(a.Dept, b.Dept),
			cmp.Compare(b.Salary, a.Salary),
			cmp.Compare(a.Name, b.Name),
		)
	})
	for _, e := range staff {
		fmt.Printf("%-6s %4d %s\n", e.Dept, e.Salary, e.Name)
	}
}

输出：

eng     150 Cy
eng     120 Ana
eng     120 Eve
sales    90 Bob
sales    90 Dee

即使第一个比较已经决定了结果，所有比较也都会执行，因为它们只是普通的参数。对字段比较来说代价很小。如果某个打破平局的比较开销很大，就手写 if c := ...; c != 0 { return c } 这样的链。

稳定排序

稳定排序会让比较结果相等的元素保持原来的顺序。当输入本身已经有意义的顺序时这一点很重要，例如按时间排好的记录，现在要按用户分组。

package main

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

type Event struct {
	User string
	Seq  int
}

func main() {
	events := []Event{
		{"bob", 1}, {"ana", 2}, {"bob", 3}, {"ana", 4}, {"bob", 5},
	}
	slices.SortStableFunc(events, func(a, b Event) int {
		return cmp.Compare(a.User, b.User)
	})
	fmt.Println(events)
}

这会打印 [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]：每个用户内部，原来的顺序保留了下来。稳定排序要做更多工作，所以只在相等元素的顺序有意义时才用它。

给 map 排序

map 没有顺序。要按键的顺序显示 map，就给它的键排序：slices.Sorted(maps.Keys(m))（Go 1.23）。要按值排序，就用一个查找值的比较函数给键排序：

package main

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

func main() {
	wordCount := map[string]int{"go": 12, "map": 3, "slice": 7, "chan": 7}

	keys := slices.Collect(maps.Keys(wordCount))
	slices.SortFunc(keys, func(a, b string) int {
		return cmp.Or(
			cmp.Compare(wordCount[b], wordCount[a]), // count, high first
			cmp.Compare(a, b),                       // then word, for a stable result
		)
	})
	for _, k := range keys {
		fmt.Println(k, wordCount[k])
	}
}

按单词打破平局很重要：没有它，chan 和 slice（都是 7）每次运行的输出顺序都可能不同，因为键从 map 中取出的顺序是随机的。更多内容见 map。

sort 包：sort.Slice 及其他函数

Go 1.21 之前，排序都通过 sort 包完成。你会在大量现有代码里看到它：

sort.Ints(nums)
sort.Strings(names)
sort.Slice(staff, func(i, j int) bool {
	return staff[i].Salary < staff[j].Salary
})
sort.SliceStable(staff, func(i, j int) bool { ... })

值得了解的区别：

sort.Slice 的一个常见 bug 是闭包捕获了另一个切片，而不是正在排序的那个，因为 less 函数是按位置取下标的。SortFunc 不会有这个 bug，因为它直接把元素交给你。

sort.Interface 类型（Len、Less、Swap）是最早的形式。对于不是单个切片的数据，例如两个必须一起移动的平行切片，它仍然是排序的方法。从 Go 1.22 起，sort.Ints、sort.Strings 和 sort.Float64s 内部直接调用 slices.Sort。

常见错误

• 以为 Sort 会返回排好序的切片。 它原地排序，不返回任何值。想要一个新的有序切片，用 slices.Sorted(slices.Values(s))，或者先 slices.Clone。
• 以为相等的元素会保持原来的顺序。 只有 Stable 系列函数保证这一点。
• 用减法做比较。 a - b 会溢出。请用 cmp.Compare。
• 给含 NaN 的浮点数排序。 cmp.Compare 把 NaN 排在所有其他值之前，让排序保持一致。手写的 a < b 比较做不到。