Explication du tri en langage Go

L'idée de tri du langage go est quelque peu différente de celle du c et du c++. c trie par défaut un tableau, c++ trie une séquence et go est plus général. L'objet à trier peut être n'importe quel objet, bien que dans de nombreux cas, il s'agisse d'une tranche (slice, similaire à un tableau) ou contient une tranche de un objet.

Trois éléments de tri (interface) :

Le nombre d'éléments à trier n

La fonction de comparaison cmp du i-ème et du j-ème éléments ;

Échange d'échange des i-ième et j-ème éléments ;

À première vue, la condition 3 est redondante, ni c ni c++ ne fournissent d'échange. Utilisation de qsort dans c : qsort(data, n, sizeof(int), cmp_int); data est l'adresse de départ, n est le nombre d'éléments, sizeof(int) est la taille de chaque élément et cmp_int est une comparaison de fonction deux entiers.

Utilisation du tri en c++ : sort(data, data+n, cmp_int); data est la position du premier élément, data+n est la position suivante du dernier élément et cmp_int est la fonction de comparaison .

Tri des types de base int, float64 et string

Tri ascendant

Pour int, Pour trier float64 et les tableaux ou tranches de chaînes, go fournit respectivement les fonctions sort.Ints(), sort.Float64s() et sort.Strings(). Par défaut, elles sont triées du plus petit au plus grand. (Il n'y a pas de fonction sort.Float32s(), ce qui est un peu étrange pour moi.)

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

Tri décroissant

int, float64 et string ont tous un ordre croissant par défaut fonctions de tri, maintenant La question est : que se passe-t-il si l'ordre est décroissant ? Toute personne ayant une expérience en programmation dans d'autres langages sait qu'il suffit d'échanger les règles de comparaison de cmp. L'implémentation de go est similaire, mais différente.

Pour trier les objets obj d'un certain Type dans go, vous pouvez utiliser sort.Sort(obj), ce qui signifie que vous devez lier trois méthodes au type Type : Len() pour trouver la longueur, Less( i,j ) est une fonction qui compare la taille des i-ème et j-ème éléments, Swap(i,j) est une fonction qui échange les i-ème et j-ème éléments.

Les trois types IntSlice, Float64Slice et StringSlice sous le package de tri implémentent respectivement ces trois méthodes. Les méthodes de tri correspondantes sont [] int, [] float64 et [] string. Si vous souhaitez trier dans l'ordre inverse, il vous suffit de modifier simplement la fonction Less correspondante.

Le package de tri de Go peut utiliser sort.Reverse(slice) pour remplacer slice.Interface.Less, qui est la fonction de comparaison. Par conséquent, la fonction de tri inversé pour int, float64 et string peut être écrite comme ceci :

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

Compréhension approfondie du tri

Il existe une interface sort.Interface dans le package de tri, qui a trois méthodes Len(), Less(i,j) et Swap(i,j) . La fonction de tri générale sort.Sort peut trier n'importe quel objet (variable) qui implémente l'interface sort.Inferface.

Pour [] int, [] float64 et [] string, en plus d'utiliser des fonctions spécialement désignées, vous pouvez également utiliser les types modifiés IntSclice, Float64Slice et StringSlice, puis appeler directement leurs méthodes Sort() correspondantes ; Parce que ces trois types implémentent également l'interface sort.Interface, vous pouvez utiliser sort.Reverse pour convertir les méthodes Interface.Less de ces trois types pour réaliser un tri inversé. Il s'agit de l'utilisation du dernier tri.

Ce qui suit utilise une structure Reverse personnalisée (définie par l'utilisateur) au lieu de la fonction sort.Reverse pour implémenter le tri inversé.

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 sont utilisés pour trier des tranches de type entier/virgule flottante/chaîne, ou des fragments, ou pas strictement des tableaux. Ensuite, il y a une fonction qui teste si c'est en ordre. Il existe également des fonctions de recherche correspondantes. Cependant, on constate que la fonction de recherche ne peut localiser la position que si elle existe. Si elle n'existe pas, la position est erronée.

Concernant le tri général des tableaux, le programme montre qu'il existe 3 méthodes ! Les trois types actuellement fournis, int, float64 et string, sont symétriques, c'est-à-dire que ce que vous avez, j'ai aussi les correspondants.

Concernant le tri inversé ou le tri inversé, utilisez simplement une structure inversée et réécrivez la fonction Less. L'inverse ci-dessus est une structure générale.

Cela dit, nous ne trions que les types de base. Il est temps de parler du tri des types de structure struct. En pratique, cela sera davantage utilisé.

Le tri des types de structure

Le tri des types de structure est réalisé en utilisant sort.Sort(slice), à ​​condition que slice soit implémenté. trois méthodes de tri. L'interface fera l'affaire. Cela dit, il existe plusieurs façons de trier. La première consiste à simuler le tri [] int pour construire le type IntSlice correspondant, puis à implémenter les trois méthodes d'Interface pour le type IntSlice.

Méthode de tri de structure 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)
 
}

Il s'agit complètement d'une méthode de simulation, donc si vous comprenez IntSlice, vous comprendrez naturellement cela, et inversement, vous comprendrez cela. Alors IntSlice comprendra.

Méthode de tri des structures 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语言教程栏目。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!