Comment implémenter le tri en langage Go

Ces dernières années, le langage Go est devenu un langage de programmation très populaire, notamment dans le développement Web et les applications cloud natives. De plus en plus de développeurs choisissent le langage Go. Parmi eux, la fonction de tri du langage Go est extrêmement puissante et peut facilement implémenter diverses fonctions de tri. Dans cet article, nous explorerons comment implémenter le tri en langage Go.

1. Tri en Golang

Le langage Go fournit le package de tri pour implémenter divers algorithmes de tri. Présentons les deux fonctions principales du package de tri. La fonction

1. sort.Slice

sort.Slice peut être utilisée pour trier des données de type Slice. Son prototype de fonction est le suivant :

func Slice(slice interface{}, less func(i, j int) bool)

Parmi eux, le paramètre slice représente la tranche. qui doit être trié, le paramètre less est une fonction de jugement et la valeur de retour doit être de type booléen. La fonction de jugement less est utilisée pour déterminer la relation de taille de chaque élément de la tranche. Si true est renvoyé, cela signifie que l'élément avant est plus petit que l'élément arrière et doit être échangé. slice参数表示需要排序的切片，less参数是一个判断函数，返回值必须是bool类型。判断函数less用于判定切片中每个元素的大小关系，如果返回true代表前面的元素比后面的元素小，需要交换位置。

以排序int类型的切片为例，示例代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    ints := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 4}
    sort.Slice(ints, func(i, j int) bool {
        return ints[i] < ints[j]
    })
    fmt.Println(ints)
}

上面的程序可以对一个int类型的切片进行排序，结果将按照从小到大的顺序排列。

2. sort.Sort

sort.Sort函数可以用来排序实现了sort.Interface接口的类型，其函数原型如下：

func Sort(data Interface)

其中，data

Prenons l'exemple du tri des tranches de type int. L'exemple de code est le suivant :

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

Le programme ci-dessus peut trier une tranche de type int, et les résultats seront classés du plus petit au plus grand. La fonction

sort.Sort

sort.Sort peut être utilisée pour trier les types qui implémentent l'interface sort.Interface. Son prototype de fonction est le suivant :

package main

import (
    "fmt"
    "sort"
)

type stringSlice []string

func (s stringSlice) Len() int {
    return len(s)
}

func (s stringSlice) Less(i, j int) bool {
    return s[i] < s[j]
}

func (s stringSlice) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {
    words := stringSlice{"foo", "bar", "baz", "qux"}
    sort.Sort(words)
    fmt.Println(words)
}

Parmi eux, le paramètre data. représente les données qui doivent être triées, ce paramètre doit être un type qui implémente l'interface sort.Interface. La définition de l'interface sort.Interface est la suivante :

package main

import "fmt"

func quickSort(arr []int, left, right int) {
    if left < right {
        partIndex := partition(arr, left, right)
        quickSort(arr, left, partIndex-1)
        quickSort(arr, partIndex+1, right)
    }
}

func partition(arr []int, left, right int) int {
    pivot := left
    for i:= left + 1; i <= right; i++ {
        if arr[i] < arr[left] {
            pivot++
            arr[pivot], arr[i] = arr[i], arr[pivot]
        }
    }
    arr[left], arr[pivot] = arr[pivot], arr[left]
    return pivot
}

func main() {
    arr := []int{5, 0, 3, 2, 1, 6, 8, 9, 7, 4}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

1. sort.Interface définit trois fonctions nécessaires au tri : Len() renvoie la longueur des données, et Less(i, j int) est utilisé pour déterminer si les données à la position i est inférieur à celui de la position j. Data, Swap(i, j int) échange les données de la position i avec les données de la position j.

Prenons l'exemple du tri d'un tableau de chaînes. L'exemple de code est le suivant :

package main

import "fmt"

func shellSort(arr []int) []int {
    n := len(arr)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            for j := i - gap; j >= 0 && arr[j] > arr[j+gap]; j -= gap {
                arr[j], arr[j+gap] = arr[j+gap], arr[j]
            }
        }
    }
    return arr
}

func main() {
    arr := []int{5, 0, 3, 2, 1, 6, 8, 9, 7, 4}
    fmt.Println(shellSort(arr))
}

Le programme ci-dessus peut trier un tableau de chaînes et les résultats seront classés du plus petit au plus grand.

• 2. Implémentation d'algorithmes de tri communs
• Dans le package de tri, des algorithmes de tri courants sont implémentés, tels que le tri rapide, le tri Hill, etc. Ces algorithmes sont implémentés sur la base de l'interface sort.Interface. les fonctions fournies par le package de tri, vous pouvez également implémenter votre propre algorithme de tri.
• Tri rapide

Le tri rapide utilise la stratégie diviser pour régner pour diviser une séquence en deux sous-séquences. Le processus spécifique est le suivant :

2. Sélectionnez un élément de la séquence comme numéro de base.

Placez tous les éléments plus petits que le numéro de base devant le numéro de base et placez les éléments plus grands que le numéro de base après le numéro de base.

Répétez les étapes ci-dessus pour les deux sous-séquences avant et après le numéro de référence.

Ce qui suit est un exemple de code pour un tri rapide :

rrreee

🎜Tri par colline🎜🎜🎜Le tri par colline, également connu sous le nom d'algorithme de tri incrémentiel descendant, est une implémentation plus efficace du tri par insertion, qui combine les éléments à trier Diviser en plusieurs groupes et effectuez respectivement le tri par insertion. Le tri final est complété en réduisant progressivement le nombre de groupes et en augmentant l'espacement des éléments au sein des groupes. 🎜🎜Ce qui suit est un exemple de code pour le tri Hill : 🎜rrreee🎜 3. Résumé 🎜🎜Cet article présente les méthodes et les algorithmes de tri couramment utilisés pour implémenter le tri dans le langage Go. Le tri rapide et le tri Hill sont l'un des plus couramment utilisés. Les algorithmes de tri sont des méthodes de mise en œuvre relativement efficaces. Lorsqu'ils utilisent le package de tri, les développeurs doivent remplacer les trois méthodes de sort.Interface. Pour certaines structures de données plus complexes, ils peuvent également implémenter leur propre algorithme de tri pour terminer l'opération de tri. 🎜

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!