An in depth understanding of golang's basic type sorting and slice sorting

  • 2020-06-03 06:44:26
  • OfStack

preface

In fact, the sorting idea of golang is a little different from C and C++. By default, C sorts arrays, C++ sorts a sequence, and Go is more general and can be sorted by any object, although in many cases it is an slice(sharding, similar to an array) or an object containing slice.

Three elements of sorting (interface) :

1. Number of elements to be sorted n;

2, i and j elements comparison function cmp;

3. Exchange of elements i and j swap;

At first glance, condition 3 appears redundant, with neither c nor c++ providing swap. The usage of qsort: qsort(data, n, sizeof(int), cmp_int); data is the starting address, n is the number of elements, sizeof(int) Is the size of each element, and cmp_int is a function that compares two int.

c++ sort sort(data, data+n, cmp_int); data is the location of the first element, data+n is the next location of the last element, and cmp_int is the comparison function.

Basic type sorting (int, float64, and string)

1. Ascending sorting

For int, float64, and string arrays or sharding, go provides for sorting sort.Ints() , sort.Float64s() and sort.Strings() The default is to sort from small to large.


package main

import (
 "fmt"
 "sort"
)

func main() {
 intList := [] int {2, 4, 3, 5, 7, 6, 9, 8, 1, 0}
 float8List := [] float64 {4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}
 stringList := [] string {"a", "c", "b", "d", "f", "i", "z", "x", "w", "y"}

 sort.Ints(intList)
 sort.Float64s(float8List)
 sort.Strings(stringList)

 fmt.Printf("%v\n%v\n%v\n", intList, float8List, stringList)

}

2. Descending sort

int, float64, and string all have ascending sort functions by default. Now the question is what about descending? As anyone with programming experience in other languages knows, just swap the comparison rules for cmp, which is implemented in a similar but different way. obj sort an Type object in go sort.Sort(obj) There are three methods to bind Type type: Len() Find the length, Less(i,j) function to compare the size of i and j elements, Swap(i,j) Function to swap i and j elements. The three types of IntSlice, Float64Slice and StringSlice in sort package implement the three methods respectively, and the corresponding sorting is [] int, [] float64 and [] string. If you want to sort in reverse order, simply change the corresponding Less function by 1.

go's sort package is available sort.Reverse(slice) To change the sizeof(int) 0 , which is the comparison function. Therefore, the reverse sorting function of int, float64 and string can be written as follows:


package main

import (
 "fmt"
 "sort"
)

func main() {
 intList := [] int {2, 4, 3, 5, 7, 6, 9, 8, 1, 0}
 float8List := [] float64 {4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}
 stringList := [] string {"a", "c", "b", "d", "f", "i", "z", "x", "w", "y"}

 sort.Sort(sort.Reverse(sort.IntSlice(intList)))
 sort.Sort(sort.Reverse(sort.Float64Slice(float8List)))
 sort.Sort(sort.Reverse(sort.StringSlice(stringList)))

 fmt.Printf("%v\n%v\n%v\n", intList, float8List, stringList)
}

3. Get a deeper understanding of sorting

The sort package has an ES118en. Interface interface with three methods Len() , Less(i,j) and Swap(i,j) . The general sorting function sort. Sort can sort any implementation sort.Inferface The object (variable) of the interface. In addition to using specially specified functions for [] int, [] float64, and [] string, you can also use modified types IntSclice, Float64Slice, and StringSlice, and then call their corresponding ones directly Sort() Methods; Because these three types are also implemented sort.Interface Interface, so it can pass sort.Reverse To convert these three types Interface.Less Method to implement the reverse sort, which is how the last sort was used.

The following USES a custom (user-defined) Reverse structure instead sort.Reverse Function to achieve the reverse sort.


package main

import (
 "fmt"
 "sort"
)

//  The custom of  Reverse  type 
type Reverse struct {
 sort.Interface //  In this way, Reverse Can accept any realization sort.Interface The object of 
}

// Reverse  I'm just going to take one of them  Inferface.Less  The order is reversed 1 Under the 
func (r Reverse) Less(i, j int) bool {
 return r.Interface.Less(j, i)
}

func main() {
 ints := []int{5, 2, 6, 3, 1, 4}

 sort.Ints(ints)          //  Special sorting function, ascending 
 fmt.Println("after sort by Ints:\t", ints)

 doubles := []float64{2.3, 3.2, 6.7, 10.9, 5.4, 1.8}

 sort.Float64s(doubles)
 fmt.Println("after sort by Float64s:\t", doubles) // [1.8 2.3 3.2 5.4 6.7 10.9]

 strings := []string{"hello", "good", "students", "morning", "people", "world"}
 sort.Strings(strings)
 fmt.Println("after sort by Strings:\t", strings) // [good hello mornig people students world]

 ipos := sort.SearchInts(ints, -1) // int  search 
 fmt.Printf("pos of 5 is %d th\n", ipos)

 dpos := sort.SearchFloat64s(doubles, 20.1) // float64  search 
 fmt.Printf("pos of 5.0 is %d th\n", dpos)

 fmt.Printf("doubles is asc ? %v\n", sort.Float64sAreSorted(doubles))

 doubles = []float64{3.5, 4.2, 8.9, 100.98, 20.14, 79.32}
 // sort.Sort(sort.Float64Slice(doubles)) // float64  Sorting method  2
 // fmt.Println("after sort by Sort:\t", doubles) // [3.5 4.2 8.9 20.14 79.32 100.98]
 (sort.Float64Slice(doubles)).Sort()   // float64  Sorting method  3
 fmt.Println("after sort by Sort:\t", doubles)  // [3.5 4.2 8.9 20.14 79.32 100.98]

 sort.Sort(Reverse{sort.Float64Slice(doubles)}) // float64  The reverse order 
 fmt.Println("after sort by Reversed Sort:\t", doubles)  // [100.98 79.32 20.14 8.9 4.2 3.5]
}

sort.Ints / sort.Float64s / sort.Strings Sort integer/floating point/string slice separately. And then there's a function that tests if it's ordered. There are corresponding search functions respectively. However, it is found that the search function can only locate to the location if it exists. If it does not exist, the location is wrong.

There are three ways to sort arrays like 1, as shown in the program! The three types of int, float64 and string currently available are symmetrical, which is what you have, and corresponding to which I also have. In terms of flip sort or reverse sort, I'm just going to rewrite it with a flip structure Less() Functions.

Reverse above is a generic structure.

With all that said, just sorting the basic types, it's time to talk about sorting the struct struct types, which are actually used more often.

Sorting of structure types

Sorting of struct types is done by using sort.Sort(slice) As long as slice is implemented sort.Interface Three of them will do. That being said, there are several ways to sort things. First, the simulation sort [] int constructs the corresponding IntSlice type, and then implements three methods of Interface for IntSlice type.

1. Simulate IntSlice sorting


package main

import (
 "fmt"
 "sort"
)

type Person struct {
 Name string
 Age int
}

//  In accordance with the  Person.Age  Sort from big to small 
type PersonSlice [] Person

func (a PersonSlice) Len() int {   //  rewrite  Len()  methods 
 return len(a)
}
func (a PersonSlice) Swap(i, j int){  //  rewrite  Swap()  methods 
 a[i], a[j] = a[j], a[i]
}
func (a PersonSlice) Less(i, j int) bool { //  rewrite  Less()  Method,   Sort from big to small 
 return a[j].Age < a[i].Age
}

func main() {
 people := [] Person{
  {"zhang san", 12},
  {"li si", 30},
  {"wang wu", 52},
  {"zhao liu", 26},
 }

 fmt.Println(people)

 sort.Sort(PersonSlice(people)) //  In accordance with the  Age  In reverse order 
 fmt.Println(people)

 sort.Sort(sort.Reverse(PersonSlice(people))) //  In accordance with the  Age  Sort in ascending order 
 fmt.Println(people)

}

This is exactly one way of simulating it, so if you understand IntSlice you understand this, and if you understand this you understand IntSlice.

The disadvantage of this method is that the PersonSlice method needs to be redefined according to the Age sorting, binding the Len, Less and Swap methods, and three functions need to be rewritten if the order is based on Name. If the structure has 4 fields and has 4 types of sorting, write 3 × 4 = 12 methods, even if 1 per cent is completely redundant, OES192en "... The real difference lies in the Less method. Therefore, Less can be abstracted out. Each sort of Less makes it dynamic, such as the following method.

2. Packaged as Wrapper


package main

import (
 "fmt"
 "sort"
)

type Person struct {
 Name string
 Age int
}

type PersonWrapper struct {     // Note here 
 people [] Person
 by func(p, q * Person) bool
}

func (pw PersonWrapper) Len() int {   //  rewrite  Len()  methods 
 return len(pw.people)
}
func (pw PersonWrapper) Swap(i, j int){  //  rewrite  Swap()  methods 
 pw.people[i], pw.people[j] = pw.people[j], pw.people[i]
}
func (pw PersonWrapper) Less(i, j int) bool { //  rewrite  Less()  methods 
 return pw.by(&pw.people[i], &pw.people[j])
}

func main() {
 people := [] Person{
  {"zhang san", 12},
  {"li si", 30},
  {"wang wu", 52},
  {"zhao liu", 26},
 }

 fmt.Println(people)

 sort.Sort(PersonWrapper{people, func (p, q *Person) bool {
  return q.Age < p.Age // Age  Decreasing order 
 }})

 fmt.Println(people)
 sort.Sort(PersonWrapper{people, func (p, q *Person) bool {
  return p.Name < q.Name // Name  sorting 
 }})

 fmt.Println(people)

}

This approach encapsulates [] Person and the criteria for comparison, cmp, into the PersonWrapper function, on which the Len, Less, and Swap methods are then bound. In fact sort.Sort(pw) The sorting is people in pw, which is what we said earlier. The sorting of go is not necessarily for an array or slice, but for an array or slice in an object.

3. Step 1 encapsulation

The sense method 2 is already quite good, except for 11 disadvantages. When used in main, it exposes the use of ES221en.Sort, and the construction of PersonWrapper. To make main more convenient to use, me can simply encapsulate 1 and construct an SortPerson method, as follows:


package main

import (
 "fmt"
 "sort"
)

type Person struct {
 Name string
 Age int
}

type PersonWrapper struct {
 people [] Person
 by func(p, q * Person) bool
}

type SortBy func(p, q *Person) bool

func (pw PersonWrapper) Len() int {   //  rewrite  Len()  methods 
 return len(pw.people)
}
func (pw PersonWrapper) Swap(i, j int){  //  rewrite  Swap()  methods 
 pw.people[i], pw.people[j] = pw.people[j], pw.people[i]
}
func (pw PersonWrapper) Less(i, j int) bool { //  rewrite  Less()  methods 
 return pw.by(&pw.people[i], &pw.people[j])
}

//  Encapsulated into  SortPerson  methods 
func SortPerson(people [] Person, by SortBy){
 sort.Sort(PersonWrapper{people, by})
}

func main() {
 people := [] Person{
  {"zhang san", 12},
  {"li si", 30},
  {"wang wu", 52},
  {"zhao liu", 26},
 }

 fmt.Println(people)

 sort.Sort(PersonWrapper{people, func (p, q *Person) bool {
  return q.Age < p.Age // Age  Decreasing order 
 }})

 fmt.Println(people)

 SortPerson(people, func (p, q *Person) bool {
  return p.Name < q.Name // Name  sorting 
 })

 fmt.Println(people)

}

The SortPerson function is constructed on the basis of method 2, and one [] Person and one cmp function are passed in use.

4. Another way of thinking


package main

import (
 "fmt"
 "sort"
)

type Person struct {
 Name  string
 Weight  int
}

type PersonSlice []Person

func (s PersonSlice) Len() int { return len(s) }
func (s PersonSlice) Swap(i, j int)  { s[i], s[j] = s[j], s[i] }

type ByName struct{ PersonSlice } //  will  PersonSlice  Wrap up to  ByName  In the 

func (s ByName) Less(i, j int) bool  { return s.PersonSlice[i].Name < s.PersonSlice[j].Name } //  will  Less  Bound to the  ByName  on 


type ByWeight struct{ PersonSlice } //  will  PersonSlice  Wrap up to  ByWeight  In the 
func (s ByWeight) Less(i, j int) bool { return s.PersonSlice[i].Weight < s.PersonSlice[j].Weight } //  will  Less  Bound to the  ByWeight  on 

func main() {
 s := []Person{
  {"apple", 12},
  {"pear", 20},
  {"banana", 50},
  {"orange", 87},
  {"hello", 34},
  {"world", 43},
 }

 sort.Sort(ByWeight{s})
 fmt.Println("People by weight:")
 printPeople(s)

 sort.Sort(ByName{s})
 fmt.Println("\nPeople by name:")
 printPeople(s)

}

func printPeople(s []Person) {
 for _, o := range s {
  fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
 }
}

I'll stop there for the moment in sorting structures. The first sort is appropriate for sorting by only one field, and the other three are for sorting by possibly more than one field. In method 4, I think it is inconvenient to construct one more ByXXX each time, so it is better to pass one more cmp in method 2 and method 3. There is no big difference between method 2 and method 3. Method 3 simply encapsulates method 1, which is more convenient for users and less error.

conclusion

Above is all about golang basic type sort and slice sort content, hope the content of this article to ah you study or use Golang can be helpful, if you have any questions you can also leave a message exchange, this site will give you a reply as soon as possible.


Related articles: