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.