65.Slice处理工具【Sort、Contains、Find】

在Go语言中，Slice是非常重要且使用频率极高的数据结构，但标准库对于Slice结构提供的方法很少。因此对于常见的排序、包含、查找等，我们可以自己提前写好工具包，方便要用的时候直接取用。

一、排序

1、sort包介绍

该包内部实现了插入排序，归并排序，堆排序和快速排序，但并不对外公开，即并不需要我们通过参数传入具体使用何种排序算法，而是在使用的时候会自动选择高效的排序算法。

外部Slice结构在使用的时候需要实现sort.Interface定义的三个方法

• Len():获取集合长度
• Less():比较两个元素大小的
• Swap():交换两个元素位置。

sort包对切片类型提供了完整的支持，主要包括

• 对基本数据类型切片的排序支持
• 基本数据元素查找
• 判断基本数据类型切片是否已经排好序
• 对排好序的数据集合逆序

2、对自定义结构体集合进行排序

package main
import (
	"fmt"
	"sort"
)
// 学生成绩结构体
type StuScore struct {
	name  string    // 姓名
	score int   // 成绩
}
type StuScores []StuScore
//Len()获取集合长度
func (s StuScores) Len() int {
	return len(s)
}
//Less(): 两个集合元素进行比较，return true不执行Swap(),false执行。
// 可简单记为小于号则是从小到大排序，因为i位置的元素在前面，不和后面j位置更大的元素交换
func (s StuScores) Less(i, j int) bool {
	return s[i].score < s[j].score
}

//Swap()对的两个元素制定移动规则
func (s StuScores) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}
func main() {
	stus := StuScores{
		{"alan", 95},
		{"hikerell", 91},
		{"acmfly", 96},
		{"leao", 90},
	}
	// 打印未排序的 stus 数据
	fmt.Println("Default:\n\t",stus)
	//StuScores 已经实现了 sort.Interface 接口 , 所以可以调用 Sort 函数进行排序
	sort.Sort(stus)
	// 判断是否已经排好顺序，将会打印 true
	fmt.Println("IS Sorted?\n\t", sort.IsSorted(stus))
	// 打印排序后的 stus 数据
	fmt.Println("Sorted:\n\t",stus)
}

输出结果：

Default:
	 [{alan 95} {hikerell 91} {acmfly 96} {leao 90}]
IS Sorted?
	 true
Sorted:
	 [{leao 90} {hikerell 91} {alan 95} {acmfly 96}]

3、sort包的相关函数

1. sort.Reverse():可以允许将数据按 Less() 定义的排序方式逆序排序，而不必修改 Less() 代码。

例如sort.Sort(sort.Reverse(stus))实现逆序。

//内部实现
// 定义了一个 reverse 结构类型，嵌入 Interface 接口
type reverse struct {
    Interface
}

//内部的Less()与自定义的Less()有着相反的逻辑
func (r reverse) Less(i, j int) bool {
    return r.Interface.Less(j, i)
}

// 返回新的实现 Interface 接口的数据类型
func Reverse(data Interface) Interface {
    return &reverse{data}
}
// 把stus传入到Recerse()方法中，返回在reverse结构体中的Interface,
// 然会外部调用Less的时候实际上是调用reverse结构体实现的Less方法，这个Less()方法与外部的有着相反的逻辑
sort.Sort(sort.Reverse(stus))//
fmt.Println(stus)

2. sort.Search():

//方法定义
func Search(n int, f func(int) bool) int
// 该方法会使用“二分查找”算法来找出能使 f(x)(0<=x<n) 返回 ture 的最小值 i,即返回切片[0:n]索引对应元素第一个符合f函数的元素。 
// 前提条件 ，切片已经是有序的: 即f(x)(0<=x<i) 均返回 false, f(x)(i<=x<n) 均返回 ture。 如果不存在 i ,则返回 n。
x := 11
s := []int{3, 6, 8, 11, 45} // 注意已经升序排序
pos := sort.Search(len(s), func(i int) bool { return s[i] >= x })

if pos < len(s) && s[pos] == x {
    fmt.Println(x, " 在 s 中的位置为：", pos)
} else {
    fmt.Println("s 不包含元素 ", x)
}

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

1、IntSlice 类型及[]int 排序

内部实现
由于[]int 切片排序内部实现及使用方法与[]float64 和[]string 类似，所以只详细描述该部分。

//IntSlice 类型及[]int 排序
//sort包定义了一个 IntSlice 类型，并且实现了 sort.Interface 接口：
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] }

//IntSlice 类型定义了 Sort() 方法，包装了 sort.Sort() 函数
func (p IntSlice) Sort() { Sort(p) }
//IntSlice 类型定义了 SearchInts() 方法，包装了 SearchInts() 函数
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

//并且提供的 sort.Ints() 方法使用了该 IntSlice 类型：所以直接使用该方法即可进行排序
func Ints(a []int) { Sort(IntSlice(a)) }

func Ints(a []int) { Sort(IntSlice(a)) }:默认升序排序

s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Ints(s)
fmt.Println(s) // 将会输出[1 2 3 4 5 6]
//使用Reverse方法进行降序
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s) // 将会输出[6 5 4 3 2 1]

func SearchInts(a []int, x int) int :查找切片中元素，需要提前进行升序排序

2、Float64Slice 类型及[]float64 排序与IntSlice类似

go内部实现

type Float64Slice []float64

func (p Float64Slice) Len() int           { return len(p) }
func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) }
func (p Float64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p Float64Slice) Sort() { Sort(p) }
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }

与 Sort()、IsSorted()、Search() 相对应的三个方法：

func Float64s(a []float64)  
func Float64sAreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int

3、StringSlice 类型及[]string 排序

内部实现

type StringSlice []string

func (p StringSlice) Len() int           { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p StringSlice) Sort() { Sort(p) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }

与 Sort()、IsSorted()、Search() 相对应的三个方法：

func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int

5、自定义结构体的简单化排序

sort.Slice():不稳定排序

    people := []struct {
    Name string
    Age  int
}{
    {"Gopher", 7},
    {"Alice", 55},
    {"Vera", 24},
    {"Bob", 75},
}

sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age }) // 按年龄升序排序
fmt.Println("Sort by age:", people)

sort.SliceStable():稳定排序，原集合中相同数据排序后仍然保持原集合的顺序

   people := []struct {
    Name string
    Age  int
}{
    {"Gopher", 7},
    {"Alice", 55},
    {"Vera", 24},
    {"Bob", 75},
}

sort.SliceStable(people, func(i, j int) bool { return people[i].Age > people[j].Age }) // 按年龄降序排序
fmt.Println("Sort by age:", people)

sort.SliceIsSorted():该函数根据自定义的规则判断集合是否为有序.

   people := []struct {
    Name string
    Age  int
}{
    {"Gopher", 7},
    {"Alice", 55},
    {"Vera", 24},
    {"Bob", 75},
}

sort.Slice(people, func(i, j int) bool { return people[i].Age > people[j].Age }) // 按年龄降序排序
fmt.Println("Sort by age:", people)
fmt.Println("Sorted:",sort.SliceIsSorted(people,func(i, j int) bool { return people[i].Age < people[j].Age }))

sort.Search():该函数判断集合是否存在指定元素，举个栗子：

a := []int{2, 3, 4, 200, 100, 21, 234, 56}
x := 21

sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })   // 升序排序
index := sort.Search(len(a), func(i int) bool { return a[i] >= x }) // 查找元素

if index < len(a) && a[index] == x {
    fmt.Printf("found %d at index %d in %v\n", x, index, a)
} else {
    fmt.Printf("%d not found in %v,index:%d\n", x, a, index)
}

二、包含Contains

我们这里就写几个常见类型的，其他的类似

func ContainsString(s []string, v string) bool {
	for _, vv := range s {
		if vv == v {
			return true
		}
	}
	return false
}


func ContainsInt(s []int, v int) bool {
	for _, vv := range s {
		if vv == v {
			return true
		}
	}
	return false
}

func ContainsInt64(s []int64, v int64) bool {
	for _, vv := range s {
		if vv == v {
			return true
		}
	}
	return false
}

func ContainsFloat64(s []float64, v float64) bool {
	for _, vv := range s {
		if vv == v {
			return true
		}
	}
	return false
}

需要注意的是ContainsFloat64函数，对于浮点数的比较很多情况下我们不会用==号，而是对比两个浮点数相减是都小于某个很小的数

三、查找Find

对于查找，我们不是说列表中有某个指定的元素，那是上面介绍的包含，这里的查找指的是包含符合某条件的元素。既然要看列表中的元素是否符合某个元素，所以需要传递一个函数作为参数。

同样，也只给出常用类型的。

返回第一个符合条件的元素和索引。用-1表示列表中没有符合给定条件的元素。

func FindString(s []string, f func(v string) bool) (string, int) {
	for index, value := range s {
		result := f(value)
		if result {
			return value, index
		}
	}
	return "", -1
}

func FindInt(s []int, f func(v int) bool) (int, int) {
	for index, value := range s {
		result := f(value)
		if result {
			return value, index
		}
	}
	return 0, -1
}

func FindInt64(s []int64, f func(v int64) bool) (int64, int) {
	for index, value := range s {
		result := f(value)
		if result {
			return value, index
		}
	}
	return 0, -1
}

func FindFloat64(s []float64, f func(v float64) bool) (float64, int) {
	for index, value := range s {
		result := f(value)
		if result {
			return value, index
		}
	}
	return 0.0, -1
}