Сортировка слайса в 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}]: внутри каждого пользователя исходная последовательность сохраняется. Стабильная сортировка делает больше работы, поэтому используйте её, только когда порядок равных элементов важен.

Сортировка мапы

У мап нет порядка. Чтобы показать мапу, отсортированную по ключу, отсортируйте её ключи: 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) печатались бы в разном порядке от запуска к запуску, потому что ключи выходят из мапы в случайном порядке. Подробнее на странице о мапах.

Пакет 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: функция «меньше» замыкается на другой слайс, а не на тот, что сортируется, ведь она обращается по позиции. У SortFunc такого бага быть не может, потому что она отдаёт вам сами элементы.

Тип 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.
• Сортировка float с NaN. cmp.Compare ставит NaN перед всеми остальными значениями, и сортировка остаётся согласованной. Самописное сравнение a < b так не умеет.