Golang Sort排序

sort包提供了排序切片和用户自定义数据集以及相关功能的函数。

集合排序

使用sort包的函数进行排序时，集合需要实现 sort.Inteface 接口，该接口中有三个方法：Len、Less、Swap。

// An implementation of Interface can be sorted by the routines in this package.
// The methods refer to elements of the underlying collection by integer index.
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)
}

sort包已经支持的内部数据类型排序

sort包原生支持[]int、[]float64 和 []string 三种内建数据类型切片的排序操作，已实现相关的Len()、Less()、Swap()方法。

// Convenience types for common cases

type IntSlice []int
type Float64Slice []float64
type StringSlice []string
...

例子

package main

import (
	"fmt"
	"sort"
)

type Student struct {
	name string
	age  int
}

func (s *Student) String() string {
	return fmt.Sprintf("(%s, %d)", s.name, s.age)
}

type StudentSlice []*Student

func (list StudentSlice) Len() int {
	return len(list)
}

func (list StudentSlice) Less(i, j int) bool {
	//排序规则：首先按年龄排序（由小到大），年龄相同时按姓名进行排序（按字符串的自然顺序）
	if list[i].age < list[j].age {
		return true
	} else if list[i].age > list[j].age {
		return false
	} else {
		return list[i].name < list[j].name
	}
}

func (list StudentSlice) Swap(i, j int) {
	list[i], list[j] = list[j], list[i]
}

func main() {
	// []int
	a := []int{1, 2, 9, 0, 5, 7, 6, 3, 4, 8}
	sort.Sort(sort.IntSlice(a))
	fmt.Println(a)

	// []float
	b := []float64{1.1, 2.2, 3.4, 2.8, 1.2, 4.5, -6.1, -0.6, -4.0, 2.4}
	sort.Sort(sort.Float64Slice(b))
	fmt.Println(b)

	// []string
	c := []string{"f", "c", "d", "b", "a", "z", "x", "y"}
	sort.Sort(sort.StringSlice(c))
	fmt.Println(c)

	s := StudentSlice([]*Student{
		&Student{"f", 18},
		&Student{"c", 17},
		&Student{"d", 19},
		&Student{"b", 16},
		&Student{"a", 15},
		&Student{"z", 18},
		&Student{"x", 18},
		&Student{"y", 17},
	})
	sort.Sort(s)
	fmt.Println(s)
}

执行结果

[0 1 2 3 4 5 6 7 8 9]
[-6.1 -4 -0.6 1.1 1.2 2.2 2.4 2.8 3.4 4.5]
[a b c d f x y z]
[(a, 15) (b, 16) (c, 17) (y, 17) (f, 18) (x, 18) (z, 18) (d, 19)]

逆排序

sort.Reverse()

例子

package main

import (
	"fmt"
	"sort"
)

func main() {
	// []int
	a := []int{1, 2, 9, 0, 5, 7, 6, 3, 4, 8}
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	fmt.Println(a)
}

执行结果

[9 8 7 6 5 4 3 2 1 0]

Reverse 源码分析

sort.Reverse 源码如下，可以发现 sort.Reverse 方法返回的是 reverse 类型的 Interface，而该结构体只是重新实现了 Less 方法。

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

IntSlice 的 Less 方法实现如下

func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }

上述 []int 类型切片排序的时候，r.Interface.Less(j, i) ，调用了 IntSlice 的 Less 方法，交换了下标 i, j。这样 Less 方法实际如下，这样就实现了逆排序

func (x IntSlice) Less(i, j int) bool { return x[j] < x[i] }