Sorting explanation in go language

#The sorting idea of ​​go language is somewhat different from c and c. c defaults to sorting an array, c sorts a sequence, and go is more general. The object to be sorted can be any object, although in many cases it is a slice (slice, similar to an array), or contains a slice of an object.

Three elements of sorting (interface):

The number of elements to be sorted n;

The comparison function cmp of the i-th and j-th elements;

Exchange swap of the i-th and j-th elements;

At first glance, condition 3 is redundant, and neither c nor c provides swap. Usage of qsort in c: 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 comparison of two ints The function.

c The usage of sort: sort(data, data n, cmp_int); data is the position of the first element, data n is the next position of the last element, and cmp_int is the comparison function.

Sort of basic types int, float64 and string

Ascending sort

For int, For sorting float64 and string arrays or slices, go provides sort.Ints(), sort.Float64s() and sort.Strings() functions respectively. By default, they are sorted from small to large. (There is no sort.Float32s() function, which is a bit strange for me.)

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}
    // float4List := [] float32 {4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}    // no function : sort.Float32s
    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)
 
}

Descending sort

int, float64 and string all have default ascending sort functions, now The question is what if the order is descending? Anyone with programming experience in other languages ​​knows that you only need to exchange the comparison rules of cmp. The implementation of go is similar, but different.

To sort the object obj of a certain Type in go, you can use sort.Sort(obj), which means you need to bind three methods to the Type type: Len() to find the length, Less(i,j ) is a function that compares the size of the i-th and j-th elements, Swap(i,j) is a function that swaps the i-th and j-th elements.

The three types IntSlice, Float64Slice, and StringSlice under the sort package implement these three methods respectively, and the corresponding sorting methods are [] int, [] float64, and [] string. If you want to sort in reverse order, you only need to simply modify the corresponding Less function.

Go's sort package can use sort.Reverse(slice) to replace slice.Interface.Less, which is the comparison function. Therefore, the reverse sorting function for int, float64 and string can be written like this:

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)
}

In-depth understanding of sorting

There is a sort.Interface interface in the sort package, which has three methods Len(), Less(i,j) and Swap(i,j) . The general sorting function sort.Sort can sort any object (variable) that implements the sort.Inferface interface.

For [] int, [] float64 and [] string, in addition to using specially designated functions, you can also use modified types IntSclice, Float64Slice and StringSlice, and then directly call their corresponding Sort() methods; Because these three types also implement the sort.Interface interface, you can use sort.Reverse to convert the Interface.Less methods of these three types to achieve reverse sorting. This is the use of the last sorting.

The following uses a custom (user-defined) Reverse structure instead of the sort.Reverse function to implement reverse sorting.

package main
 
import (
    "fmt"
    "sort"
)
 
// 自定义的 Reverse 类型
type Reverse struct {
    sort.Interface    // 这样， Reverse 可以接纳任何实现了 sort.Interface (包括 Len, Less, Swap 三个方法) 的对象
}
 
// Reverse 只是将其中的 Inferface.Less 的顺序对调了一下
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)                                     // 特殊排序函数， 升序
    fmt.Println("after sort by Ints:\t", ints)  // [1 2 3 4 5 6]
 
    doubles := []float64{2.3, 3.2, 6.7, 10.9, 5.4, 1.8}
 
    sort.Float64s(doubles)                                      // float64 排序版本 1
    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 搜索
    fmt.Printf("pos of 5 is %d th\n", ipos)     // 并不总是正确呀 ! (搜索不是重点)
 
    dpos := sort.SearchFloat64s(doubles, 20.1)    // float64 搜索
    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 排序方法 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 排序方法 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 逆序排序
    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 are used to sort integer/floating point/string type slices, or fragments, or not strictly arrays. Then there is a function that tests whether it is in order. There are also corresponding search functions. However, it is found that the search function can only locate the position if it exists. If it does not exist, the position is wrong.

Regarding general array sorting, the program shows that there are 3 methods! The three types currently provided, int, float64 and string, are symmetrical, that is, what you have, I also have the corresponding ones.

Regarding flip sorting or reverse sorting, just use a flip structure and rewrite the Less function. The Reverse above is a general structure.

So much has been said above, only the basic types are sorted. It’s time to talk about the sorting of struct structure types. In practice, this will be used more.

Sorting of structure types

Sorting of structure types is achieved by using sort.Sort(slice), as long as slice is implemented The three methods of sort.Interface will do. Having said that, there are several ways to sort. The first is to simulate sorting [] int to construct the corresponding IntSlice type, and then implement the three methods of Interface for the IntSlice type.

Structure sorting method 1

package main
 
import (
    "fmt"
    "sort"
)
 
type Person struct {
    Name string    // 姓名
    Age  int    // 年纪
}
 
// 按照 Person.Age 从大到小排序
type PersonSlice [] Person
 
func (a PersonSlice) Len() int {    // 重写 Len() 方法
    return len(a)
}
func (a PersonSlice) Swap(i, j int){     // 重写 Swap() 方法
    a[i], a[j] = a[j], a[i]
}
func (a PersonSlice) Less(i, j int) bool {    // 重写 Less() 方法， 从大到小排序
    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))    // 按照 Age 的逆序排序
    fmt.Println(people)
 
    sort.Sort(sort.Reverse(PersonSlice(people)))    // 按照 Age 的升序排序
    fmt.Println(people)
 
}

This is completely a simulation method, so if you understand IntSlice, you will naturally understand this, and conversely, you will understand this. Then IntSlice will understand.

Structure sorting method 2

方法 1 的缺点是 ： 根据 Age 排序需要重新定义 PersonSlice 方法，绑定 Len 、 Less 和 Swap 方法， 如果需要根据 Name 排序， 又需要重新写三个函数； 如果结构体有 4 个字段，有四种类型的排序，那么就要写 3 × 4 = 12 个方法， 即使有一些完全是多余的， 仔细思量一下，根据不同的标准 Age 或是 Name， 真正不同的体现在 Less 方法上，所以， me 们将 Less 抽象出来， 每种排序的 Less 让其变成动态的，比如下面一种方法。

package main
 
import (
    "fmt"
    "sort"
)
 
type Person struct {
    Name string    // 姓名
    Age  int    // 年纪
}
 
type PersonWrapper struct {
    people [] Person
    by func(p, q * Person) bool
}
 
func (pw PersonWrapper) Len() int {    // 重写 Len() 方法
    return len(pw.people)
}
func (pw PersonWrapper) Swap(i, j int){     // 重写 Swap() 方法
    pw.people[i], pw.people[j] = pw.people[j], pw.people[i]
}
func (pw PersonWrapper) Less(i, j int) bool {    // 重写 Less() 方法
    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 递减排序
    }})
 
    fmt.Println(people)
    sort.Sort(PersonWrapper{people, func (p, q *Person) bool {
        return p.Name < q.Name    // Name 递增排序
    }})
 
    fmt.Println(people)
 
}

方法 2 将 [] Person 和比较的准则 cmp 封装在了一起，形成了 PersonWrapper 函数，然后在其上绑定 Len 、 Less 和 Swap 方法。 实际上 sort.Sort(pw) 排序的是 pw 中的 people， 这就是前面说的， go 的排序未必就是针对的一个数组或是 slice， 而可以是一个对象中的数组或是 slice 。

结构体排序方法 3

me 赶脚方法 2 已经很不错了， 唯一一个缺点是，在 main 中使用的时候暴露了 sort.Sort 的使用，还有就是 PersonWrapper 的构造。 为了让 main 中使用起来更为方便， me 们可以再简单的封装一下， 构造一个 SortPerson 方法， 如下：

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 {    // 重写 Len() 方法
    return len(pw.people)
}
func (pw PersonWrapper) Swap(i, j int){     // 重写 Swap() 方法
    pw.people[i], pw.people[j] = pw.people[j], pw.people[i]
}
func (pw PersonWrapper) Less(i, j int) bool {    // 重写 Less() 方法
    return pw.by(&pw.people[i], &pw.people[j])
}
 
 
func SortPerson(people [] Person, by SortBy){    // SortPerson 方法
    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 递减排序
    }})
 
    fmt.Println(people)
 
    SortPerson(people, func (p, q *Person) bool {
        return p.Name < q.Name    // Name 递增排序
    })
 
    fmt.Println(people)
 
}

在方法 2 的基础上构造了 SortPerson 函数，使用的时候传过去一个 [] Person 和一个 cmp 函数。

结构体排序方法 4

下面是另外一个实现思路， 可以说是方法 1、 2 的变体。

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 }    // 将 PersonSlice 包装起来到 ByName 中
 
func (s ByName) Less(i, j int) bool     { return s.PersonSlice[i].Name < s.PersonSlice[j].Name }    // 将 Less 绑定到 ByName 上
 
 
type ByWeight struct{ PersonSlice }    // 将 PersonSlice 包装起来到 ByWeight 中
func (s ByWeight) Less(i, j int) bool   { return s.PersonSlice[i].Weight < s.PersonSlice[j].Weight }    // 将 Less 绑定到 ByWeight 上
 
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)
    }
}

更多go语言知识请关注PHP中文网go语言教程栏目。

The above is the detailed content of Sorting explanation in go language. For more information, please follow other related articles on the PHP Chinese website!