golang自定义sort及延展知识？

背景介绍

初来乍到

刚入门golang的时候，总是不知道怎么才能实现自定义类型的排序。
这几天看leader面试别人，时不时也会问到排序的问题，看来还是很重要的。
这篇小文章，一起小结下自定义类型的排序问题。

本文摘要

• 自定义排序的实现；
• 先按A规则排序再按B规则排序的实现技巧；
• 三剑客原理回顾；

问题引入

如何对下面的personArr实现先按Height排序、再按Age排序呢？

type Person struct {
    Name string
    Age int
    Height int
}

personArr := make([]Person, 0)

三剑客

初识三剑客

最通用的是下面这个函数：

sort.Sort(data)

跳转到该函数的实现：

func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

在看下Interface的定义：

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

从定义可知，只要传入的data实现了Len、Less、Swap三个函数就可以直接调用sort方法了！

show me code

回到最上面自定义排序的问题，实现如下：

type []Person PersonArr

func (p PersonArr) Len() int {
    return len(p)
}

// 下面算是一个小技巧
// 先按Height排序、再按Age排序
func (p PersonArr) Less(i, j int) bool {
    if p[i].Height != p[j].Height {
        return p[i].Height < p[j].Height
    }

    return p[i].Age < p[j].Age
}

func (p PersonArr) Swap(i, j int) {
    tmp := p[i]
    p[i] = p[j]
    p[j] = tmp
}

调用示例

简单使用

personArr := PersonArr{                      
    Person{                                  
        Name: "h180_a30",                    
        Age: 30,                             
        Height: 180,                         
    },                                       
    Person{                                  
        Name: "h170_a35",                    
        Age: 35,                             
        Height: 170,                         
    },                                       
    Person{                                  
        Name: "h180_a25",                    
        Age: 25,                             
        Height: 180,                         
    },                                       
    }                                        
                                             
                                             
fmt.Printf("%+v", personArr)                 

运行结果

[{Name:h180_a30 Age:30 Height:180} {Name:h170_a35 Age:35 Height:170} {Name:h180_a25 Age:25 Height:180}]

举一反三

其他类型的排序，也和上面的大同小异了。

再挖一层

源码跟读

为什么是这三个函数，这个就要看golang中sort的实现了，

func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

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

从上面的代码可以看出，quickSort并不是只实现了快速排序，
而是根据实际数据灵活的选择快速排序、堆排序、插入排序的；

why三剑客

上面代码中最主要的篇幅是和快速排序相关的了，所以我们也简单回顾下快速排序的原理：

• 首先设定一个分界值；
• 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
• 左右两边的子数组也同样通过上面两个步骤排好序；（递归的思想）
• 将左边排序数组、分界值、右边排序数组三者连接起来，排序完成。

上面的步骤，必然会用到比较、交换、数组长度这三个基本要素，所以就必须实现三剑客了。
注：详细以及拓展阅读请参阅维基百科的介绍。

开箱即用

golang默认实现的排序有哪些？如下几个可以开箱即用：

sort.Slice()
sort.Float64s()
sort.Ints()
sort.Strings()

喜欢的话，关注我的公众号哦

本公众号关注golang、程序员出路、开心也是一种能力一种需要等。

---