golang 之 slice 排序

╰+攻爆jí腚メ 2022-05-13 08:20 159阅读 0赞

虽然 golang 自带了 sort 包，但笔者之前用的并不多，最近需要对一个 \[\]struct 的结构进行排序，顺手整理下使用的细节，以后用的时候查资料就可以啦（ps 撒花）

## 用 slice 实现归并排序 ##

由简单的 \[\]int 开始学习，假定提供一个 int 类型的 slice，需要按照顺序进行排序，猜测机智的你可能会这么实现：

func merge(left, right []int) (result []int) {
        var l, r int
        for l < len(left) && r < len(right) {
            if left[l] < right[r] {
                result = append(result, left[l])
                l++
            } else {
                result = append(result, right[r])
                r++
            }
        }
        result = append(result, left[l:]...)
        result = append(result, right[r:]...)
        return
    
    }
    
    func mergeSort(s []int) []int {
        if len(s) <= 1 {
            return s
        }
        middle := len(s) / 2
        left := mergeSort(s[:middle])
        right := mergeSort(s[middle:])
        return merge(left, right)
    }

上述的代码是**归并排序**的实现（顺道复习一下），大概用了 20 左右，性能和速度也都符合要求。但是 sort 包给一种更简单的排序方式：

sort.Sort(sort.IntSlice(slice))

*  slice: 为待排序的切片
 *  有道理相信崇尚简洁的开发工程师更喜欢用后一种

**看下结果：**

===============merge sort=============================== [3 9 10 3 5 7]
    [3 3 5 7 9 10]
    ==================sort package============================ [3 9 10 3 5 7]
    [3 3 5 7 9 10]

## 调用 sort.Slice() 排序 ##

提升点难度，假设 slice 中存储是一个自定义的结构体，假设定义的结构体格式是，待排序的是 Value 字段，results 为待排序的切片 \[\]result：

type result struct {
        IP    string  `json:"IP"`
        Value float64 `json:"Value"`
    }

使用 sort 提供的排序接口，可按照如下的方式排序：

sort.Slice(results, func(i, j int) bool {
            return results[i].Value < results[j].Value
    
    })

## 实现 sort 排序的接口 ##

除了上面的排序方式，也可以自定义类型，然后实现排序需要的接口(Len、Less、Swap），按照如下方式实现：

type byValue []result
    
    func (v byValue) Len() int {
        return len(v)
    }
    
    func (v byValue) Swap(i, j int) {
        v[i], v[j] = v[j], v[i]
    }
    
    func (v byValue) Less(i, j int) bool {
        return v[i].Value < v[j].Value
    }

然后在排序的切片上调用 sort.Sort 函数即可：

sort.Sort(byValue(results))

## 引入第三方包排序 ##

本着以人为本，多构思代码，少写代码的精神，上面的操作可以用第三方包[github.com/patrickmn/sortutil][github.com_patrickmn_sortutil]来实现：

sortutil.AscByField(results, "Value")

*  详细的使用可以看 github 上的描述
 *  map 排序，需要将 key（或者 value）拷贝到一个切片，再对切片排序，按照上面写的几种方式就可以啦
 *  上述三种方式的排序速度，笔者测下来是 **实现 sort 的排序接口** > **调用 sort.Slice 排序** > **引入第三方包**
 *  猜测第三方包比较慢的原因是因为实现的时候用了很多反射的语法，具体原因待查明

## 参考资料 ##

*  [https://groups.google.com/forum/\#!topic/golang-nuts/EZ9yGIw0IeI][https_groups.google.com_forum_topic_golang-nuts_EZ9yGIw0IeI]
 *  [https://github.com/patrickmn/sortutil][github.com_patrickmn_sortutil]

## 完整代码 ##

package main
    
    import (
        "encoding/json"
        "fmt"
        "net/http"
        "sort"
        "time"
    
        "github.com/pmylund/sortutil"
    )
    
    type result struct {
        IP    string  `json:"IP"`
        Value float64 `json:"Value"`
    }
    
    type byValue []result
    
    func (v byValue) Len() int {
        return len(v)
    }
    
    func (v byValue) Swap(i, j int) {
        v[i], v[j] = v[j], v[i]
    }
    
    func (v byValue) Less(i, j int) bool {
        return v[i].Value < v[j].Value
    }
    
    func main() {
        resp, err := http.Get("gengerate result struct url")
        if err != nil {
            fmt.Println(err)
            return
        }
        defer resp.Body.Close()
        results := make([]result, 0)
    
        err = json.NewDecoder(resp.Body).Decode(&results)
        if err != nil {
            fmt.Println(err)
            return
        }
        t := time.Now()
        sort.Slice(results, func(i, j int) bool {
            return results[i].Value < results[j].Value
    
        })
    
        sortutil.AscByField(results, "Value")
        sort.Sort(byValue(results))
        for _, v := range results {
            fmt.Printf("k: %s, v:%f\n", v.IP, v.Value)
        }
        fmt.Printf("used time: %v\n", time.Since(t))
    }

[github.com_patrickmn_sortutil]: https://github.com/patrickmn/sortutil
[https_groups.google.com_forum_topic_golang-nuts_EZ9yGIw0IeI]: https://groups.google.com/forum/#!topic/golang-nuts/EZ9yGIw0IeI