What are the implementation methods of sort package in Go language?

Go is a strongly typed language, its code is concise and easy to read, and it has efficient performance, so it is becoming more and more popular among developers. Among them, the sort package is an important part of the Go language standard library. It provides sorting functions for slices and user-defined collection types. This article will introduce the implementation of the sort package in the Go language.

The definition of the sort.Interface interface in the sort package is as follows:

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

Through this interface, we can implement a custom type of sorting algorithm.

In the sort package, there are three main sorting methods implemented: Sort, Stable, and Slice, which will be introduced one by one below.

1. Sort

The Sort method sorts the incoming slices and uses an optimized quick sort algorithm. It can be seen from the source code: the type of the slice is []Type, so you can use the Type slice to directly call the Sort method (Type is the internal element type of the slice).

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

The Sort method internally calls the quickSortFunc function to perform the sorting operation. The function will call itself recursively until the recursion is completed or the divided sub-slice is too small.

// 快速排序
// 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

The Stable method is a stable sorting algorithm that can keep the relative positions of equal elements unchanged. This operation is mainly to sort some slices that do not comply with the sorting rules of the Sort method in a relatively orderly manner, such as the semi-sorting of the elements in the figure.

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

This algorithm is very efficient. It is not only a stable sorting algorithm, but also has a complexity of O(n log n).

3. Slice

Slice sorts sub-slices, that is, sorts slices [start, end). You can use this method to sort all iterators supported by slices.

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

It should be noted that the implementation of the less function method must be implemented according to the Less method of sort.Interface. The less function will pass in two indexes i and j and return a bool value: determine whether the element i is less than Element j, if yes, then swap(i, j).

The above is a brief implementation of the sort package in the Go language. From the above introduction, we can find that the sort package is relatively simple to implement, but has efficient sorting performance and provides great convenience to developers.

The above is the detailed content of What are the implementation methods of sort package in Go language?. For more information, please follow other related articles on the PHP Chinese website!