golang中排序的底层逻辑

golang中排序最底层的逻辑是是这段代码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.Interface，下面是它的定义

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

也就意味着，所有想要使用快速排序算法来排序的类型，只要实现了sort.Interface接口，就可以使用sort.Sort方法来排序。

内建的排序方法

在定制排序规则之前，我们先来看下golang的官方包中包含的基本排序方法

strArr := []string{"hello", "5", "world", "0", "golang", "123"}
sort.Strings(strArr)
fmt.Println(strArr)	//	输出 [0 123 5 golang hello world]

官方包中提供了sort.Strings()来给字符串slice排序，sort.Ints()给整型slice排序，等等。

自定义排序规则

假设我想实现的逻辑是在已有的字符串排序规则之上，让数字出现在最后，我就可以通过定义一个类并实现sort.Interface来实现

type NumberLastStringSlice []string

func (x NumberLastStringSlice) Len() int { return len(x) }
func (x NumberLastStringSlice) Less(i, j int) bool {
	xIsDigit := unicode.IsDigit([]rune(x[i])[0])
	jIsDigit := unicode.IsDigit([]rune(x[j])[0])

	if (xIsDigit && jIsDigit) || (!xIsDigit && !jIsDigit) {
		return x[i] < x[j]
	}

	return !xIsDigit
}
func (x NumberLastStringSlice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }

sort.Sort(NumberLastStringSlice(strArr))
fmt.Println(strArr)		// 输出 [golang hello world 0 123 5]