sort包使用

今天阅读Go标准库的sort包，这个包是实现排序功能的

使用示例

func main() {
    a := []string{"bag", "cat", "apple", "dog"}
    fmt.Println("before sort:", a)
    sort.Strings(a)  //对字符串切片排序
    // 也可以这样调用 sort.StringSlice(a).Sort() 
    fmt.Println("after sort:", a)

    b := []int{1, 3, 5, 2, 4, 6}
    fmt.Println("before sort:", b)
    sort.Ints(b)  //对整数切片排序
    // 也可以这样调用 sort.IntSlice(a).Sort() 
    fmt.Println("after sort:", b)

    c := []float64{2.0, 1.5, 3.3, 0.8}
    fmt.Println("before sort:", c)
    sort.Float64s(c)  //对浮点数切片排序
    // 也可以这样调用 sort.Float64Slice(a).Sort() 
    fmt.Println("after sort:", c)
}

// 输出
before sort: [bag cat apple dog]
after sort: [apple bag cat dog]
before sort: [1 3 5 2 4 6]
after sort: [1 2 3 4 5 6]
before sort: [2 1.5 3.3 0.8]
after sort: [0.8 1.5 2 3.3]

源码解析

1、sort 包定义了Interface接口，包含一下三个方法，只要实现了这个接口，就可以调用sort包中的排序方法。

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

2、示例中的IntSlice，StringSlice，Float64Slice 等类型都实现了Interface接口，以 IntSlice为例，如下：

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int

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

// Sort is a convenience method.
func (p IntSlice) Sort() { Sort(p) }

// Ints sorts a slice of ints in increasing order.
func Ints(a []int) { Sort(IntSlice(a)) }

• sort.Ints(b)的调用其实就是先转换参数b的类型为IntSlice然后调用自身的Sort()方法，然后IntSlice类型有Sort()方法，所以sort.IntSlice(b).Sort()调用是可以的

3、sort.Sort()方法属于sort包暴露出来的核心调用方法，如下：

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}

• sort.Sort()对data进行排序。它调用一次data.Len()来决定排序的长度n，调用 data.Less 和data.Swap()的开销为O(n*log(n))。

• 此排序为不稳定排序。他根据不同形式决定使用不同的排序方式（插入排序，堆排序，快排）

• 因此，一个类型只要实现了Interface接口，就可以调用 sort.Sort()方法对其进行排序。

• 此处Interface是sort包自行定义的接口，区别interface，前文提到过，并且sort.Sort()默认排序后是升序的

4、由于sort.Sort()方法默认排序为升序，所以sort包也提供了降序的方法sort.Reverse()，如下：

type reverse struct {
	// This embedded Interface permits Reverse to use the methods of
	// another Interface implementation.
	Interface
}

// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
	return &reverse{data}
}

• 这里通过一个reverse的struct，实现了一个对Interface新封装，通过修改新增reverse.Less()方法，将i,j两个参数互换顺序从而实现降序排序，实在是骚操作了-，-
• 由于是已经改变了传入对象的类型，所以不能重复调用sort.Reverse()fangfa

5、源码的简单部分就这些，后续再考虑深入阅读，例如自动选择排序方法的实现，以及对实现Inrerface接口的对象的一些附加操作。

用法总结

1、简单类型

[]int,[]string,[]float64，直接类型转换为sort包的内置类型即可，以[]int为例如下：

// 快速使用
sort.Ints([]int{})
// 转换使用
sort.IntSlince([]int{}).Sort()

2、自定义类型

首先实现Interface接口，然后如简单类型调用即可，示例：

func reconstructQueue(people [][]int) [][]int {
	re := make([][]int, 0)
	sort.Sort(heightAndRank(people))
	for _, v := range people {
		insert(&re, v, v[1])
	}
	return re
}

func insert(re *[][]int, h []int, k int) {
	*re = append(*re, []int{})
	copy((*re)[k+1:], (*re)[k:])
	(*re)[k] = h
}
//自定义类型
type heightAndRank [][]int

//实现Interface接口

func (r heightAndRank) Len() int {
	return len(r)
}

func (r heightAndRank) Less(i, j int) bool {
	// 对h进行判断 按照降序排序
	if r[i][0] > r[j][0] {
		return true
	}
	if r[i][0] < r[j][0] {
		return false
	}
	// 对j进行判断 按照升序进行排序
	return r[i][1] < r[j][1]
}

func (r heightAndRank) Swap(i, j int) {
	r[i], r[j] = r[j], r[i]
}

• 以上代码是leetcode 406题的解法，首先是思路是将二维数组[][]int按照h降序，k升序来排序，（PS：分别h为第一个参数，k为第二个参数，对应r[i][0]以及r[i][1]），然后遍历排序后的数组，通过拆入来实现需要得到的顺序，此处用到sort包
• 此处用到sort包实现排序部分，排序的重点其实在于Less()方法的实现，源码注释说明该方法是判断索引为i的元素是否小于索引为j的元素，我们将其修改反向判断h即可实现h的降序，如果h相同则判断k，实现k的升序
• 单独测试排序效果：

//修改reconstructQueue方法
func reconstructQueue(people [][]int) [][]int {
	sort.Sort(heightAndRank(people))
	return people
}
func main(){
    re := reconstructQueue([][]int{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}})
	fmt.Print(re)
}

//输出
[[7 0] [7 1] [6 1] [5 0] [5 2] [4 4]]