Was sind die Implementierungsmethoden des Sortierpakets in der Go-Sprache?

Go ist eine stark typisierte Sprache, ihr Code ist prägnant und leicht zu lesen und sie verfügt über eine effiziente Leistung, weshalb sie bei Entwicklern immer beliebter wird. Unter anderem ist das Sortierpaket ein wichtiger Bestandteil der Standardbibliothek der Go-Sprache. Es bietet Sortierfunktionen für Slices und benutzerdefinierte Sammlungstypen. In diesem Artikel wird die Implementierung des Sortierpakets in der Go-Sprache vorgestellt.

Die Definition der Schnittstelle sort.Interface im Sortierpaket lautet wie folgt:

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

Über diese Schnittstelle können wir einen benutzerdefinierten Typ von Sortieralgorithmus implementieren.

Im Sortierpaket sind drei Hauptsortiermethoden implementiert: Sortieren, Stabil und Slice, die im Folgenden einzeln vorgestellt werden.

1. Sortieren

Die Sortiermethode sortiert die eingehenden Slices und verwendet einen optimierten Schnellsortierungsalgorithmus. Aus dem Quellcode ist ersichtlich: Der Typ des Slice ist []Type, sodass Sie das Type-Slice verwenden können, um die Sort-Methode direkt aufzurufen (Type ist der interne Elementtyp des Slice).

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

Die Sort-Methode ruft intern die Funktion quickSortFunc auf, um den Sortiervorgang auszuführen. Die Funktion ruft sich selbst rekursiv auf, bis die Rekursion abgeschlossen ist oder das geteilte Teilsegment zu klein ist.

// 快速排序
// 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. Die stabile Methode ist ein stabiler Sortieralgorithmus, der die relativen Positionen gleicher Elemente unverändert lassen kann. Bei dieser Operation werden hauptsächlich einige Slices, die nicht den Sortierregeln der Sort-Methode entsprechen, relativ geordnet sortiert, z. B. die Halbsortierung der Elemente in der Abbildung.

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

Dieser Algorithmus ist nicht nur ein stabiler Sortieralgorithmus, sondern hat auch eine Komplexität von O(n log n).

3. Slice

Slice sortiert Unter-Slices, also Slices [Start, Ende). Mit dieser Methode können Sie alle von Slices unterstützten Iteratoren sortieren.

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

Es ist zu beachten, dass die Implementierung der Less-Funktionsmethode gemäß der Less-Methode von sort.Interface implementiert werden muss. Die Less-Funktion übergibt zwei Indizes i und j und gibt einen Bool-Wert zurück: Bestimmen Sie, ob das Element i ist kleiner als das Element j. Wenn ja, swap(i, j).

Das Obige ist eine kurze Implementierung des Sortierpakets in der Go-Sprache. Aus der obigen Einführung können wir ersehen, dass das Sortierpaket relativ einfach zu implementieren ist, aber eine effiziente Sortierleistung aufweist und Entwicklern auch großen Komfort bietet.

Das obige ist der detaillierte Inhalt vonWas sind die Implementierungsmethoden des Sortierpakets in der Go-Sprache?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!