В этом посте мы рассмотрим различные способы сортировки фрагмента с помощью пакета sort из стандартной библиотеки Go.

Сортировка по возрастанию

Чтобы отсортировать фрагмент в порядке возрастания, мы можем использовать Ints(x), Float64(x) и Strings(x) из пакета sort.

Примеры:

  • Сортировка int
nums := []int{3, 7, 8, 1, 5, 4}
sort.Ints(nums)
fmt.Println(nums) // prints [1 3 4 5 7 8]
  • Сортировка float64
floats := []float64{3.2, 7.1, 7.9, 1.1, 5.2, 3.9}
sort.Float64s(floats)
fmt.Println(floats) // prints [1.1 3.2 3.9 5.2 7.1 7.9]
  • Сортировка string
strings := []string{"apple", "Banana", "cherry", "Mango", "papaya"}
sort.Strings(strings)
fmt.Println(strings) // [Banana Mango apple cherry papaya]

Обратите внимание, что sort.Strings(x) сортирует элементы в фрагменте строки на основе их значения Unicode, поэтому все заглавные буквы идут первыми.

Вот как вы можете сортировать в порядке возрастания с помощью Go. Довольно просто и удобно, правда?

Но это не так просто, когда нам нужно что-то кроме сортировки по возрастанию, например, сортировка фрагментов в порядке убывания.

Давайте рассмотрим 2 других способа сортировки для решения этой проблемы.

Сортировка с пользовательским компаратором с использованием sort.Slice

sort.Slice() сортирует срез с предоставленной функцией less. Но что такое функция less?

Less сообщает, должен ли элемент с индексом i сортироваться перед элементом с индексом j.

Сигнатура функции выглядит так:

less(i, j int) bool

Теперь вернемся к нашему примеру. Мы можем отсортировать срез в порядке убывания следующим образом:

nums := []int{3, 7, 8, 1, 5, 4}
sort.Slice(nums, func(i, j int) bool {
  return nums[i] > nums[j]
})
fmt.Println(nums) // prints [8 7 5 4 3 1]

К этому моменту вы уже должны догадаться, как реализована функция less в sort.Ints. Проверь!

Если вы действительно перейдете по ссылке, вы заметите закономерность во встроенных функциях сортировки.

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int
func (x IntSlice) Len() int           { return len(x) }
func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x IntSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
// Float64Slice implements Interface for a []float64, sorting in increasing order,
// with not-a-number (NaN) values ordered before other values.
type Float64Slice []float64
func (x Float64Slice) Len() int { return len(x) }
func (x Float64Slice) Less(i, j int) bool { return x[i] < x[j] || (isNaN(x[i]) && !isNaN(x[j])) }
func (x Float64Slice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
// StringSlice attaches the methods of Interface to []string, sorting in increasing order.
type StringSlice []string
func (x StringSlice) Len() int           { return len(x) }
func (x StringSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x StringSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

Это потому, что они реализуют интерфейс sort.Interface. Да, интерфейс называется Interface.

И это подводит нас к последнему разделу, сортировке с использованием sort.Sort().

Сортировка sort.Interface с помощью sort.Sort()

Эта опция обеспечивает максимальную настройку и на самом деле является основой того, как все функции сортировки работают в пакете sort.

Например, sort.Ints на самом деле:

func Ints(x []int) { Sort(IntSlice(x)) }

Вы также можете проверить исходный код.

Теперь давайте попробуем понять, что делает функция sort.Sort().

Из документов:

func Sort(data Interface)

sort.Sort() сортирует данные в порядке возрастания, как определено методом Less. Он делает один вызов data.Len для определения n и O(n*log(n)) вызовов data.Less и data.Swap. Стабильность сортировки не гарантируется.

data.Len, data.Less, data.Swap исходят из интерфейса sort.Interface, которые выглядят так:

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

Реализуя sort.Interface, мы также можем вызывать sort.Sort() для нашей коллекции.

Например, давайте создадим пользовательскую структуру, реализующую интерфейс:

type Pet struct {
	name string
	kind string
}
type PetSlice []Pet
func (p PetSlice) Len() int {
	return len(p)
}
func (p PetSlice) Less(i, j int) bool {
	return p[i].name < p[j].name // sort in ascending order using the pet's name
}
func (p PetSlice) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

Затем мы можем использовать нашу пользовательскую структуру следующим образом:

var myPets PetSlice = []Pet{
  {"luna", "cat"},
  {"hery", "dog"},
  {"dory", "fish"},
}
fmt.Println(myPets) // [{luna cat} {hery dog} {dory fish}]
sort.Sort(myPets)
fmt.Println(myPets) // [{dory fish} {hery dog} {luna cat}]

Каждый раз, когда вы вызываете sort.Sort для myPets, myPets будет сортироваться с использованием метода Less в качестве компаратора.

Наконец, вернемся к нашему примеру с сортировкой int slice в порядке убывания. Мы также можем реализовать собственный тип для этого.

type myIntSlice []int
func (s myIntSlice) Len() int {
	return len(s)
}
func (s myIntSlice) Less(i, j int) bool {
	return s[i] > s[j]
}
func (s myIntSlice) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

И используйте это так:

var nums myIntSlice = []int{3, 7, 8, 1, 5, 4}
sort.Sort(nums)
fmt.Println(nums) // [8 7 5 4 3 1]

Конечно, нам не всегда нужно объявлять нашу переменную с нашим пользовательским типом. Мы также можем использовать приведение типов для ситуации, когда данные уже есть.

В любое время, когда нам нужно отсортировать слайс int в порядке убывания, мы можем просто привести его к нашему пользовательскому типу.

nums := []int{3, 7, 8, 1, 5, 4}
sort.Sort(myIntSlice(nums))
fmt.Println(nums) // [8 7 5 4 3 1]

"Заворачивать"

Это все для этого поста. Я надеюсь, что он послужит вам кратким руководством по пакету sort.