Quelles sont les méthodes d'implémentation du package de tri en langage Go ?

Go est un langage fortement typé, son code est concis et facile à lire, et ses performances sont efficaces, il devient donc de plus en plus populaire parmi les développeurs. Parmi eux, le package de tri est une partie importante de la bibliothèque standard du langage Go. Il fournit des fonctions de tri pour les tranches et les types de collections définis par l'utilisateur. Cet article présentera l'implémentation du package sort dans le langage Go.

La définition de l'interface sort.Interface dans le package sort est la suivante :

type Interface interface {
    // 嵌入内置的len函数，返回集合元素个数
    Len() int
    // 比较索引i和索引j上的元素
    Less(i, j int) bool
    // 交换索引i和索引j上的元素
    Swap(i, j int)
}

Grâce à cette interface, nous pouvons implémenter un type d'algorithme de tri personnalisé.

Dans le package de tri, trois méthodes de tri principales sont implémentées : Sort, Stable et Slice, qui seront présentées une par une ci-dessous.

1. Sort

La méthode Sort trie les tranches entrantes et utilise un algorithme de tri rapide optimisé. Cela peut être vu dans le code source : le type de la tranche est []Type, vous pouvez donc utiliser la tranche Type pour appeler directement la méthode Sort (Type est le type d'élément interne de la tranche).

func Sort(data Interface) {
    n := data.Len()
    quickSortFunc(n, swapFunc(data), maxDepth(n))
}

La méthode Sort appelle en interne la fonction quickSortFunc pour effectuer l'opération de tri. La fonction s'appellera de manière récursive jusqu'à ce que la récursion soit terminée ou que la sous-tranche divisée soit trop petite.

// 快速排序
// n 为切片大小
// swap 为交换函数，可以通过sort.Interface中的swap方法来实现
func quickSortFunc(n int, swap swapFunc, maxDepth int) {
    // 插入排序，Num^1为偶数，&1可用来判断奇偶性
    if n < insertionSortThreshold {
        for i := 1; i < n; i++ {
            for j := i; j > 0 && swap(j-1, j); j-- {
            }
        }
        return
    }
    if maxDepth == 0 {
        heapSortFunc(n, swap)
        return
    }
    maxDepth--
    third := n / 2
    // 选择枢纽元
    if n > med3Threshold {
        m0 := 0
        m1 := n / 2
        m2 := n - 1
        if n > 40 {
            s := n / 8
            m0 = med3(swap, 0, s, 2*s)
            m1 = med3(swap, m1-s, m1, m1+s)
            m2 = med3(swap, n-1-2*s, n-1-s, n-1)
        }
        third = med3(swap, m0, m1, m2)
    }
    // 挖洞填数
    // z正反代表着大或小于枢纽元素
    z := n - 1
    // p代表在枢纽元素左边的指针，q代表在枢纽元素右边的指针
    p := 0
    q := z
    for {
        for ; p < n && !swap(p, third); p++ {
        }
        for ; q >= 0 && swap(q, third); q-- {
        }
        if p >= q {
            break
        }
        swap(p, q)
        if p == third {
            third = q
        } else if q == third {
            third = p
        }
        p++
        q--
    }
    // 对子切片递归调用quickSortFunc函数
    quickSortFunc(p, swap, maxDepth)
    quickSortFunc(n-p-1, swapFuncAt(swap, p+1), maxDepth)
}

2. Stable

La méthode Stable est un algorithme de tri stable qui peut maintenir inchangées les positions relatives d'éléments égaux. Cette opération consiste principalement à trier certaines tranches qui ne respectent pas les règles de tri de la méthode Sort de manière relativement ordonnée, comme le semi-tri des éléments de la figure.

func Stable(data Interface) {
    // length 为切片长度
    length := data.Len()
    // mergeSort函数就是归并排序
    mergeSort(data, 0, length)
}

Cet algorithme est très efficace. Ce n'est pas seulement un algorithme de tri stable, mais il a également une complexité de O(n log n).

3. Slice

Slice trie les sous-tranches, c'est-à-dire trie les tranches [début, fin).

func Slice(slice interface{}, less func(i, j int) bool) {
    // 利用反射获取slice值信息
    rv := reflect.ValueOf(slice)
    // 获取长度信息
    vlen := rv.Len()
    // 初始化并调用SortInterface，参数为lessSlice
    reflect.Sort(newSortInterface(rv, makeLessSlice(less, vlen)))
}

Il est à noter que l'implémentation de la méthode less doit être implémentée selon la méthode Less de sort.Interface. La fonction less passera dans deux index i et j et retournera une valeur booléenne : déterminer si l'élément i est plus petit que l'élément j. Si c'est le cas, swap(i, j).

Ce qui précède est une brève implémentation du package de tri dans le langage Go. D'après l'introduction ci-dessus, nous pouvons constater que le package de tri est relativement simple à implémenter, mais a des performances de tri efficaces et offre également aux développeurs une grande commodité.

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!