Comment implémenter un algorithme de tri rapide dans Go

Le tri rapide est un algorithme de tri classique. Son efficacité de tri est très élevée et la complexité temporelle est O(n*logn). Parmi les différents langages de programmation, la nouvelle génération de langages représentée par Go propose également diverses implémentations de tri rapide. Cet article présentera comment implémenter l'algorithme de tri rapide dans Go.

L'idée de base de l'algorithme de tri rapide est que l'opération principale d'un tri rapide consiste à sélectionner un élément spécifique (x) (peut être un nombre aléatoire ou le premier ou le dernier) parmi tous les éléments du tableau. , qui est appelé élément de division (pivot). Les données à trier sont divisées en deux parties indépendantes grâce à un tri en un seul passage. Tous les éléments d'une partie sont plus petits que les éléments de limite et tous les éléments de l'autre partie sont plus grands que les éléments de limite.

Plus précisément, nous pouvons mettre en œuvre un tri rapide en suivant les étapes suivantes :

• Sélectionnez un élément du tableau comme élément de comparaison (pivot).
• Mettez les éléments inférieurs ou égaux pour pivoter vers la gauche, et les éléments supérieurs à pivoter vers la droite.
• Tri rapide de manière récursive respectivement sur les côtés gauche et droit.

Le code Golang est le suivant :

package main

import "fmt"

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

func partition(arr []int, left, right int) int {
    pivot := arr[left]
    for left < right {
        for left < right && arr[right] >= pivot {
            right--
        }
        arr[left] = arr[right]
        for left < right && arr[left] <= pivot {
            left++
        }
        arr[right] = arr[left]
    }
    arr[left] = pivot
    return left
}

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

Le code ci-dessus implémente le processus de tri rapide. La fonction de partition dans le code est utilisée pour partitionner les éléments et la fonction QuickSort est utilisée pour implémenter la récursion de tri rapide. Parmi eux, les pointeurs gauche et droit se déplacent respectivement vers le milieu pour trouver le numéro qui doit être remplacé, déterminer la nouvelle position par échange et revenir à la position du pivot.

Dans la fonction principale, un tableau arr est défini, puis le résultat après un tri rapide est affiché.

En résumé, cet article nous aide à comprendre et à maîtriser l'algorithme de tri rapide en présentant les principes de base de l'algorithme de tri rapide et en implémentant le tri rapide via le code dans Golang.

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!