How to implement sort package in golang

The sort package implements three basic sorting algorithms: insertion sort. Quick sort and heap sort. As in other languages, these three methods are not public, they are only used internally by the sort package.

So users do not need to consider which sorting method to use when using the sort package to sort. There are three methods defined by sort.Interface: the Len() method to obtain the length of the data set, and the Less() method to compare the sizes of two elements. ) method and the Swap() method that exchanges the positions of two elements, you can sort the data collection smoothly. The sort package will automatically select an efficient sorting algorithm based on the actual data.

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

Any type (generally a collection) that implements sort.Interface can be sorted using the methods in this package. These methods require that the index of the listed elements within the collection be an integer.

Here I use the source code to explain the implementation directly:

1. Examples in the source code:

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 (data Interface) method

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

For more golang knowledge, please pay attention to the golang tutorial column.

The above is the detailed content of How to implement sort package in golang. For more information, please follow other related articles on the PHP Chinese website!