Comment implémenter le package de tri dans Golang

Le package de tri implémente trois algorithmes de tri de base : le tri par insertion. Tri rapide et tri en tas. Comme dans d’autres langages, ces trois méthodes ne sont pas publiques, elles ne sont utilisées qu’en interne par le package sort.

Les utilisateurs n'ont donc pas besoin de réfléchir à la méthode de tri à utiliser lorsqu'ils utilisent le package de tri pour trier. Il existe trois méthodes définies par sort.Interface : la méthode Len() pour obtenir la longueur de l'ensemble de données, et la méthode Less() pour comparer les tailles de deux éléments. ) et la méthode Swap() qui échange les positions de deux éléments, vous pouvez trier la collecte de données en douceur. Le package de tri sélectionnera automatiquement un algorithme de tri efficace basé sur les données réelles.

type Interface interface {
    // 返回要排序的数据长度
    Len() int
    //比较下标为i和j对应的数据大小，可自己控制升序和降序        
Less(i, j int) bool
    // 交换下标为i，j对应的数据
    Swap(i, j int)
}

Tout type (généralement une collection) qui implémente sort.Interface peut être trié à l'aide des méthodes de ce package. Ces méthodes nécessitent que l'index des éléments répertoriés dans la collection soit un nombre entier.

Ici, j'utilise le code source pour expliquer directement l'implémentation :

1 Exemples dans le code source :

type Person struct {
    Name string
    Age  int
}

type ByAge []Person
//实现了sort接口中的三个方法，则可以使用排序方法了
func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func Example() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    sort.Sort(ByAge(people)) //此处调用了sort包中的Sort()方法,我们看一下这个方法
    fmt.Println(people)

    // Output:
    // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
    // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
}

2.

//sort包只提供了这一个公开的公使用的排序方法，
func Sort(data Interface) {
    // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
    //如果元素深度达到2*ceil(lg(n+1))则选用堆排序
    n := data.Len()
    maxDepth := 0
    for i := n; i > 0; i >>= 1 {
        maxDepth++
    }
    maxDepth *= 2
    quickSort(data, 0, n, maxDepth)
}

//快速排序
//它这里会自动选择是用堆排序还是插入排序还是快速排序，快速排序就是
func quickSort(data Interface, a, b, maxDepth int) {
    //如果切片元素少于十二个则使用希尔插入法
    for b-a > 12 { // Use ShellSort for slices <= 12 elements
        if maxDepth == 0 {
            heapSort(data, a, b) //堆排序方法，a=0,b=n
            return
        }
        maxDepth--
        mlo, mhi := doPivot(data, a, b)
        // Avoiding recursion on the larger subproblem guarantees
        // a stack depth of at most lg(b-a).
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

//堆排序
func heapSort(data Interface, a, b int) {
    first := a
    lo := 0
    hi := b - a

    // Build heap with greatest element at top.
    //构建堆结构，最大的元素的顶部，就是构建大根堆
    for i := (hi - 1) / 2; i >= 0; i-- {
        siftDown(data, i, hi, first)
    }

    // Pop elements, largest first, into end of data.
    //把first插入到data的end结尾
    for i := hi - 1; i >= 0; i-- {
        data.Swap(first, first+i) //数据交换
        siftDown(data, lo, i, first) //堆重新筛选
    }
}

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
    //hi为数组的长度
    //这里有一种做法是把跟元素给取到存下来，但是为了方法更抽象，省掉了这部，取而代之的是在swap的时候进行相互交换
    root := lo  //根元素的下标
    for {
        child := 2*root + 1 //左叶子结点下标
        //控制for循环介绍，这种写法更简洁，可以查看我写的堆排序的文章
        if child >= hi { 
            break
        }
        //防止数组下标越界，判断左孩子和右孩子那个大
        if child+1 < hi && data.Less(first+child, first+child+1) {  
            child++
        }
        //判断最大的孩子和根元素之间的关系
        if !data.Less(first+root, first+child) {
            return
        }
        //如果上面都 满足，则进行数据交换
        data.Swap(first+root, first+child)
        root = child
    }
}

Pour plus de connaissances sur le golang, veuillez faire attention à la colonne

tutoriel 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!