Go Academy · Урок

Стабильная сортировка

Сохраняйте порядок равных элементов

Урок 4 из 413 шагов

«Стабильная сортировка» — бесплатный урок Go Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения 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.Stable для типов с интерфейсом сортировки
позволяет сортировать в несколько проходов по разным ключам

Можно начать бесплатно

Изучай Go с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы: 51
Уроки: 203

Начать учиться бесплатно Посмотреть полный курс

Часто задаваемые вопросы

Урок «Стабильная сортировка» бесплатный?

Да — полный текст урока «Стабильная сортировка» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Go Academy, подпишись на CoddyKit PRO. Курс Go Academy содержит 4 уроков всего.

Чему я научусь в уроке «Стабильная сортировка»?

Сохраняйте порядок равных элементов Ты практикуешь Go Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Go Academy?

Предыдущий опыт не требуется. Go Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Стабильная сортировка»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Go Academy?

Да. Каждый урок Go Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к Go Academy