golang's solution for sorting custom types

preface

The Go language allows us to customize types, and in real projects, we often need to sort by a field of a struct type. I didn't know how to solve this problem before. Later, I searched related problems on the Internet and found some good solutions. Please refer to here and make a summary.

Since the golang sort package itself provides the functionality, there is no need to build a wheel, so let's see how to use the sort package.

sort package, discussion

The sort package of sorting algorithm is also implemented in golang. The sort package internally implements four basic sorting algorithms: insertion sort (insertionSort), merge sort (symMerge), heap sort (heapSort) and quick sort (quickSort). The sort package automatically selects the best sorting algorithm based on actual data.

So we only need to think about the implementation when we write code sort.Interface This type will do.

Take a quick look at the sort package

func Sort(data Interface) {
 // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
 n := data.Len()
 maxDepth := 0
 for i := n; i > 0; i >>= 1 {
 maxDepth++
 }
 maxDepth *= 2
 quickSort(data, 0, n, maxDepth)
}
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)
}
//  Internally implemented 4 Sorting algorithm 
//  Insertion sort 
func insertionSort(data Interface, a, b int)
//  Heap sort 
func heapSort(data Interface, a, b int)
//  Quick sort 
func quickSort(data Interface, a, b, maxDepth int)
//  Merge sort 
func symMerge(data Interface, a, m, b int)

So I'm gonna call sort.Sort() To implement custom type sorting, we only need our type to implement the three methods in the Interface interface type.

Take a look at the sort package itself for example []int How types are sorted

//  First of all, I've defined 1 a []int Alias of a type IntSlice 
type IntSlice []int
//  Access to this  slice  The length of the 
func (p IntSlice) Len() int   { return len(p) }
//  Compare the two element sizes   ascending 
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
//  Exchange data 
func (p IntSlice) Swap(i, j int)  { p[i], p[j] = p[j], p[i] }
// sort.Ints() Internal calls Sort()  Method implementation ordering 
//  Pay attention to   The first []int  convert  IntSlice type   Because of this type is implemented Interface the 3 A method of  
func Ints(a []int) { Sort(IntSlice(a)) }

Let's follow suit and sort our custom structure types in descending order

package main
import (
 "fmt"
 "sort"
)
type Person struct {
 Name string
 Age int
}
type Persons []Person
//  Access to this  slice  The length of the 
func (p Persons) Len() int { return len(p) }
//  Sort the elements in descending order by age   (Follow your own business logic here)  
func (p Persons) Less(i, j int) bool {
 return p[i].Age > p[j].Age
}
//  Exchange data 
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func main() {
 persons := Persons{
 {
 Name: "test1",
 Age: 20,
 },
 {
 Name: "test2",
 Age: 22,
 },
 {
 Name: "test3",
 Age: 21,
 },
 }
 fmt.Println(" Before ordering ")
 for _, person := range persons {
 fmt.Println(person.Name, ":", person.Age)
 }
 sort.Sort(persons)
 fmt.Println(" After ordering ")
 for _, person := range persons {
 fmt.Println(person.Name, ":", person.Age)
 }
}

Actually, one is the same Len() and Swap() Basically nothing is changed, only the comparison of elements is involved Less() The approach will change.

What do we do when we sort more than one field in a structure? Do we write these three methods for every one sorted? Of course not. We can solve this problem with nested constructs. Because a nested structure can inherit all the properties and methods of a parent structure

For example, if I want to sort the Name field and Age pair of Person above, we can use nested constructs to improve 1.

package main
import (
 "fmt"
 "sort"
)
type Person struct {
 Name string
 Age int
}
type Persons []Person
// Len() Methods and Swap() The method does not change 
//  Access to this  slice  The length of the 
func (p Persons) Len() int { return len(p) }
//  Exchange data 
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
//  Nested structures   Will inherit  Person  All properties and methods 
//  So it's equivalent to SortByName  Also achieved  Len()  and  Swap()  methods 
type SortByName struct{ Persons }
//  Sort by the name length of the element in descending order   (Follow your own business logic here) 
func (p SortByName) Less(i, j int) bool {
 return len(p.Persons[i].Name) > len(p.Persons[j].Name)
}
type SortByAge struct{ Persons }
//  Sort the elements in descending order by age   (Follow your own business logic here) 
func (p SortByAge) Less(i, j int) bool {
 return p.Persons[i].Age > p.Persons[j].Age
}
func main() {
 persons := Persons{
 {
 Name: "test123",
 Age: 20,
 },
 {
 Name: "test1",
 Age: 22,
 },
 {
 Name: "test12",
 Age: 21,
 },
 }
 fmt.Println(" Before ordering ")
 for _, person := range persons {
 fmt.Println(person.Name, ":", person.Age)
 }
 sort.Sort(SortByName{persons})
 fmt.Println(" After ordering ")
 for _, person := range persons {
 fmt.Println(person.Name, ":", person.Age)
 }
}

conclusion