Comment classer le golang bouillonnant

Explication détaillée de l'algorithme de tri des bulles Golang

Le tri des bulles est un algorithme de tri courant. Son principe est très simple, c'est une sorte de tri d'échange. L'idée principale de cet algorithme est de comparer les tailles de deux éléments adjacents, puis d'échanger leurs positions en fonction de la relation de taille. À chaque tour, l'élément le plus grand ou le plus petit est disposé à une extrémité de la séquence. Il existe deux méthodes de mise en œuvre spécifiques : l’une de l’avant vers l’arrière et l’autre de l’arrière vers l’avant. Cet article présentera la mise en œuvre du tri des bulles dans Golang.

Tout d'abord, nous créons un tableau d'entiers et passons la fonction de tri à bulles :

package main

import "fmt"

func main() {
    arr := []int{3, 7, 1, 4, 2, 8, 5, 9, 6}
    fmt.Println("排序前:",arr)
    BubbleSort(arr)
    fmt.Println("排序后:",arr)
}

func BubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

Dans la fonction BubbleSort, nous obtenons d'abord la longueur du tableau, puis configurons deux nids de boucles. La boucle externe est une boucle sur l'ensemble du tableau et la boucle interne est une boucle sur les éléments. Dans la boucle interne, nous comparons les tailles des éléments adjacents, puis échangeons leurs positions en fonction de la relation de taille.

La méthode d'échange est implémentée via l'affectation multiple de Golang, c'est-à-dire "arr[j], arr[j+1] = arr[j+1], arr[j]". Cette instruction attribue la valeur de arr[j+1] à arr[j] et la valeur de arr[j] à arr[j+1]. De cette façon, l'échange entre deux éléments peut être complété.

Il est à noter que chaque tour de tri déplacera le plus petit ou le plus grand élément vers une extrémité de la séquence. Afin de garantir l'efficacité, nous devons soustraire le nombre d'éléments triés i dans la boucle externe, c'est-à-dire "for j := 0; j < n-1-i; j++". De cette manière, le nombre de comparaisons à chaque tour de tri n’inclura pas les éléments déjà triés.

Enfin, nous appelons la fonction BubbleSort dans la fonction principale et imprimons les résultats du tableau pré-tri et post-tri sur la console.

Ensuite, nous testons les performances de cet algorithme. Nous pouvons utiliser la propre bibliothèque de tests de Golang pour les tests. Le code de test spécifique est le suivant :

package main

import (
    "testing"
)

func TestBubbleSort(t *testing.T) {
    arr := []int{3, 7, 1, 4, 2, 8, 5, 9, 6}
    BubbleSort(arr)
    if !checkSort(arr) {
        t.Error("BubbleSort test failed")
    }
}

func checkSort(arr []int) bool {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        if arr[i] > arr[i+1] {
            return false
        }
    }
    return true
}

Dans la fonction principale, nous définissons une fonction appelée TestBubbleSort, qui est utilisée pour tester l'exactitude de la fonction BubbleSort que nous avons écrite. Dans la fonction de test, nous appelons la fonction BubbleSort et utilisons la fonction checkSort pour déterminer si le résultat du tri est correct. Si le résultat du tri est incorrect, le message d'erreur « Échec du test BubbleSort » sera affiché.

Ensuite, nous utilisons la commande go test pour exécuter le test. Entrez la commande suivante sur la ligne de commande :

go test -v -run="TestBubbleSort"

Cette commande exécutera la fonction TestBubbleSort et affichera les résultats du test sur la console. Les résultats sont les suivants :

=== RUN   TestBubbleSort
--- PASS: TestBubbleSort (0.00s)
PASS
ok      _/home/go_ws/src/gotest/src/TestBubbleSort   0.097s

Comme le montrent les résultats du test, l'algorithme de tri a réussi le test unitaire et la durée du test n'était que de 0,097 seconde. Par conséquent, l’algorithme de tri à bulles fonctionne bien en termes d’efficacité.

Résumé

Cet article présente la mise en œuvre du tri à bulles dans Golang et vérifie l'exactitude et l'efficacité de l'algorithme de tri grâce à des tests unitaires. Dans les applications pratiques, nous pouvons optimiser cet algorithme de manière appropriée selon les besoins pour obtenir de meilleurs résultats 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!