В этом посте мы рассмотрим различные способы сортировки фрагмента с помощью пакета 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
.