Go常用包(十一):sort排序和查询

1.介绍

sort包实现了四种基本排序算法：插入排序、归并排序、堆排序、快速排序。但是这四种排序方法是不公开的，它们只能在 sort 包内部使用。sort 包会根据实际数据自动选择高效的排序算法，所以在对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了 sort.Interface 定义的三个方法,就可以顺利对数据集合进行排序：

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

1.1 支持功能

sort 包对[]int 、[]float64 、[]string 切片提供了完整的支持，主要功能有：

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

2.排序

2.1 `T.Sort`

a. 使用方法

// 步骤1.定义相关类型 sort.IntSlice/Float64Slice/StringSlice
sliceExample := T{..,..,..}
// 步骤2.调用排序方法
sliceExample.Sort()
// 步骤3.判断是否已排序
if sorted := sort.IsSorted(sliceExample);sorted{
	fmt.Printf("排序成功:%+v\n",sliceExample)
} else {
	fmt.Println("排序失败！")
}

b. 代码示例

package test
import (
	"fmt"
	"sort"
	"testing"
)
func TestIntSliceSort(t *testing.T) {
	// 定义整数序列
	nums := sort.IntSlice{10,40,6,9,23,72,89}
	// 排序
	nums.Sort()
	// 判断是否已排序
	if sorted := sort.IsSorted(nums);sorted{
		fmt.Printf("排序结果:%+v\n",nums)
	} else {
		fmt.Println("排序失败！")
	}
}
/** 输出:
=== RUN   TestIntSliceSort
排序结果:[6 9 10 23 40 72 89]
--- PASS: TestIntSliceSort (0.00s)
PASS
*/

2.2 `sort.Ints`

将 []int 进行升序排序。

a. 代码示例

// 测试使用
func TestInts(t *testing.T) {
	a := []int{23,12, 9, 2, 12,3, 89}
	// 调用排序
	sort.Ints(a)
	// 检测是否已经排序
	if sorted := sort.IntsAreSorted(a); sorted {
		fmt.Printf("排序成功: %v\n",a)
	} else  {
		fmt.Printf("排序失败: %v\n",a)
	}
	// 查找元素
	fmt.Printf("查找元素(存在): %v 索引:%v \n",12,sort.SearchInts(a, 12))
	fmt.Printf("查找元素(不存在): %v 索引:%v \n",22,sort.SearchInts(a, 22))
}
/** 输出
=== RUN   TestInts
排序成功: [2 3 9 12 12 23 89]
查找元素(存在): 12 索引:3 
查找元素(不存在): 22 索引:5 
--- PASS: TestInts (0.00s)
PASS
*/

2.3 `sort.Float64s`

将 []float64 进行升序排序。

a. 代码示例

// 浮点型切片排序
func TestFloat64s(t *testing.T) {
	f := []float64{20.2,13.8,28.12,5.23}
	// 排序
	sort.Float64s(f)
	// 检测是否已经排序
	if sorted := sort.Float64sAreSorted(f); sorted {
		fmt.Printf("排序成功: %v\n",f)
	} else  {
		fmt.Printf("排序失败: %v\n",f)
	}
	// 查找元素
	searchVal1 := 13.8
	searchVal2 := 29.23
	fmt.Printf("查找元素(存在): %v 索引:%v \n",searchVal1,sort.SearchFloat64s(f, searchVal1))
	fmt.Printf("查找元素(不存在): %v 索引:%v \n",searchVal2,sort.SearchFloat64s(f, searchVal2))
}
/** 输出
=== RUN   TestFloat64s
排序成功: [5.23 13.8 20.2 28.12]
查找元素(存在): 13.8 索引:1 
查找元素(不存在): 29.23 索引:4 
--- PASS: TestFloat64s (0.00s)
PASS
*/

2.4 `sort.Strings`

将 []string 进行升序排序。

a. 代码示例

// 字符串型切片排序
func TestSlice(t *testing.T) {
	s := []string{"d", "a", "c", "e", "b"}
	// 排序
	sort.Strings(s)
	// 检测是否已经排序
	if sorted := sort.StringsAreSorted(s); sorted {
		fmt.Printf("排序成功: %v\n",s)
	} else  {
		fmt.Printf("排序失败: %v\n",s)
	}
	// 查找元素
	searchVal1 := "e"
	searchVal2 := "f"
	fmt.Printf("查找元素(存在): %v 索引:%v \n",searchVal1,sort.SearchStrings(s, searchVal1))
	fmt.Printf("查找元素(不存在): %v 索引:%v \n",searchVal2,sort.SearchStrings(s, searchVal2))
}
/** 输出
=== RUN   TestSlice
排序成功: [a b c d e]
查找元素(存在): e 索引:4 
查找元素(不存在): f 索引:5 
--- PASS: TestSlice (0.00s)
PASS
*/

2.5 降序

a.降序原理

前面介绍的都是排序规则都是升序(sort包默认都是升序),如果想要降序，可以使用sort.Reverse来调换Less()参数，从而实现降序的目的。

sort.Reverse 源码

// 接收一个Interface类型参数
func Reverse(data Interface) Interface {
	return &reverse{data}
}
// 可以看到这里是把参数 i,j 互换成 j,i
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

c.代码示例

// 测试降序使用
func TestReverseSort(t *testing.T) {
	// 使用sort包中的数据类型
	intSlice := sort.IntSlice{23, 15, 9, 2, 12, 3, 89}
	// 互换j,i
	reverse := sort.Reverse(intSlice)
	// 排序
	sort.Sort(reverse)
	fmt.Printf("排序结果: %v\n", intSlice)
}
/** 输出
=== RUN   TestReverseSort
排序结果: [89 23 15 12 9 3 2]
--- PASS: TestReverseSort (0.00s)
PASS
*/

3. 查找

3.1 查找步骤

步骤一：定义类型变量
步骤二：先排序后查找(查找是基于排序后的结果)
步骤三：查询可能存在的索引
步骤四：判断是否相等

3.2 代码示例

// 查找
func TestSearch(t *testing.T) {
	// 1.定义类型
	intSlice := sort.IntSlice{10, 40, 6, 9, 23, 72, 89}
	// 2.排序后查找
	intSlice.Sort()
	// 3.查询可能存在的索引
	searchVal := 40
	searchIndex := intSlice.Search(searchVal)
	// 4.判断是否相等
	if searchIndex > len(intSlice) {
		fmt.Printf("未找到：%v\n", searchVal)
	} else {
		if searchVal == intSlice[searchIndex] {
			fmt.Printf("找到: %v 索引为: %v \n", searchVal, searchIndex)
		} else {
			fmt.Printf("未找到：%v\n", searchVal)
		}
	}
	// 查找不存在情况
	searchVal2 := 90
	searchIndex2 := intSlice.Search(searchVal2)
	if searchIndex2 >= len(intSlice) {
		fmt.Printf("未找到：%v\n", searchVal2)
	} else {
		if searchVal2 == intSlice[searchIndex2] {
			fmt.Printf("找到: %v 索引为: %v \n", searchVal2, searchIndex2)
		} else {
			fmt.Printf("未找到：%v\n", searchVal2)
		}
	}
}

/** 输出
=== RUN   TestSearch
找到: 40 索引为: 4 
未找到：90
--- PASS: TestSearch (0.00s)
PASS
*/