So implementieren Sie ein Sortierpaket in Golang

Das Sortierpaket implementiert drei grundlegende Sortieralgorithmen: Einfügungssortierung. Schnelle Sortierung und Heap-Sortierung. Wie in anderen Sprachen sind diese drei Methoden nicht öffentlich, sie werden nur intern vom Sortierpaket verwendet.

Benutzer müssen also nicht darüber nachdenken, welche Sortiermethode sie verwenden sollen, wenn sie das Sortierpaket zum Sortieren verwenden. Es gibt drei Methoden, die durch sort.Interface definiert sind: die Len()-Methode, um die Länge des Datensatzes zu ermitteln. und der Methode Less() zum Vergleichen der Größen zweier Elemente und der Methode Swap(), die die Positionen zweier Elemente austauscht, können Sie die Datensammlung reibungslos sortieren. Das Sortierpaket wählt automatisch einen effizienten Sortieralgorithmus basierend auf den tatsächlichen Daten aus.

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

Jeder Typ (im Allgemeinen eine Sammlung), der sort.Interface implementiert, kann mit den Methoden in diesem Paket sortiert werden. Diese Methoden erfordern, dass der Index der aufgelisteten Elemente innerhalb der Sammlung eine Ganzzahl ist.

Hier verwende ich den Quellcode, um die Implementierung direkt zu erklären:

1. Beispiele im Quellcode:

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 (Datenschnittstelle)-Methode

//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
    }
}

Für mehr Golang-Wissen beachten Sie bitte die Spalte Golang-Tutorial.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie ein Sortierpaket in Golang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!