Go：Map排序

Golang使用接口实现任意对象的排序。

Map是一个非常实用的数据结构，能够将一个唯一key映射到特定类型对象。在查询Map里面的内容时，其时间复杂度为O(1)非常高效。然而，Map的一个缺点就是不能直接排序。如今的一些编程语言以某种方式来实现map的排序，例如python3.7+可以通过一个lambda函数实现map的排序。

在Go语言当中，可以使用接口和sort包通过几个步骤实现map的排序。实现map排序有很多方法，但这种实现sort接口的方式是我最喜欢的。

1、创建自定义类型来表示key和value及其组合列表

为了能保存排序后的值，必须创建两种类型来表示Map的key和value。Pair结构体包含Key和Value属性，与Map的键值对应。举个例子，有一个map定义为map[string]bool{}，底层包含一个string类型的key和bool类型的value。假设，key和value都是int类型的话。可以定义如下结构体：

type Pair struct {
    Key int
    Value int
}

type PairList []Pair

以上代码定义了PairList切片，存放哈希映射map[int]int所有键值对内容。

2、PairList实现sort.Interface接口

前面已经定义了属性值来表示map的键值对的结构体，下面让对应的切片类型PairList实现sort.Interface。要实现该接口的话，需要实现以下几个函数：

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int

    // Less reports whether the element with index i
    // must sort before the element with index j.
    //
    // If both Less(i, j) and Less(j, i) are false,
    // then the elements at index i and j are considered equal.
    // Sort may place equal elements in any order in the final result,
    // while Stable preserves the original input order of equal elements.
    //
    // Less must describe a transitive ordering:
    //  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
    //  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
    //
    // Note that floating-point comparison (the < operator on float32 or float64 values)
    // is not a transitive ordering when not-a-number (NaN) values are involved.
    // See Float64Slice.Less for a correct implementation for floating-point values.
    Less(i, j int) bool

    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

要实现任意对象的排序，只需要实现以上接口的3个函数即可，然后调用sort.Sort()方法就可以实现值排序。下面我们将PairList类型实现以上接口：

func (p PairList) Len() int { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Value < p[j].Value }
func (p PairList) Swap(i, j int){ p[i], p[j] = p[j], p[i] }

如果你想实现key的排序而不是value排序，仅需要修改Less()方法即可。你也可以修改swap函数可以实现值的递减排序。感谢Go接口，让很多功能都实现很简单。

3、将map的键值对转换为切片，然后排序输出。

这里我们初始化一个someMap对象来演示map的排序。我们定义pairList表示切片用于存储map的键值对，其长度和map相等。通过for循环将所有键值对存放到切片里面。

someMap := map[int]int{
    0: 2,
    3: 7,
    9: 3,
    1: 5,
    7: 6,
}
pairList := make(PairList, len(someMap))

pairListIdx := 0
for k, v := range(someMap) {
    pairList[pairListIdx] = Pair{k,v}
    pairListIdx++
}

fmt.Println(someMap)
fmt.Println("Unsorted PairList:", pairList)
sort.Sort(pairList)
fmt.Println("Sorted PairList:", pairList)

如果你要在函数中运行这段代码，输出将是:

map[0:2 1:5 3:7 7:6 9:3]
Unsorted PairList: [{1 5} {7 6} {0 2} {3 7} {9 3}]
Sorted PairList: [{0 2} {9 3} {1 5} {7 6} {3 7}]

现在，您已经学会了如何对任意数据结构通过实现sort.Sort接口来进行排序。