排序 参考:Golang sort包排序(详细全集) 方法一 :sort.Slice()方法 package main import ( "fmt" "sort" ) func main() { arr := []int{8, 3, 5, 7, 1, 4} sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] }) fmt.Println(arr) } 方法二:在一开始时创建具有排序方法的切片 package main import ( "fmt" "sort" ) func main() { arr := sort.IntSlice{8, 3, 5, 7, 1, 4} arr.Sort() fmt.Println(arr) } 方法三 :对自定义结构体的排序 package main import ( "fmt" "sort" ) type Point struct { x, y int } type Points []Point func (p Points) Len() int { return len(p) } func (p Points) Less(i, j int) bool { if p[i].x != p[j].x { return p[i].x < p[j].x } return p[i].y < p[j].y } func (p Points) Swap(i, j int) { p[i], p[j] = p[j], p[i] } func main() { arr := Points{{1, 2}, {1, 3}, {2, 3}} sort.Sort(arr) fmt.Println(arr) } 注意:默认的 sort() 会自动选择快排、堆排序和插入排序,是不稳定排序,如果需要稳定排序,请使用 sort.Stable()(其使用的是归并排序) 二分查找 对一个完整的有序数组进行二分查找 package main import ( "fmt" "sort" ) func main() { // 定义一个有序切片 nums := []int{1, 2, 3, 3, 3, 4, 5, 6, 7} // 查找第一个大于 3 的元素的下标 index := sort.Search(len(nums), func(i int) bool { return nums[i] > 3 }) fmt.Println("upper_bound index:", index) // 查找第一个大于等于 3 的元素的下标 index = sort.Search(len(nums), func(i int) bool { return nums[i] >= 3 }) fmt.Println("lower_bound index:", index) } 对子切片中的元素进行二分查找,可通过改造 Search()函数的参数实现 package main import ( "fmt" "sort" ) //LowerBound /* * @input int st 起始位置 * @input int ed 结束位置的后一位 * @input int key 查找元素 * @input []int arr 查找的数组 * @return int 要查找的元素在子切片中的相对位置,在原切片中的位置为st+index */ func LowerBound(st, ed int, key int, arr []int) (index int) { return sort.Search(ed-st, func(i int) bool { return arr[st+i] >= key }) } func UpperBound(st, ed int, key int, arr []int) (index int) { return sort.Search(ed-st, func(i int) bool { return arr[st+i] > key }) } func main() { // 定义一个已排序的切片 nums := []int{1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 10} //index为在子切片中的位置,对应原切片st+index index := LowerBound(2, 8, 5, nums) fmt.Println("lower_bound index:", index) index = UpperBound(2, 8, 5, nums) fmt.Println("upper_bound index:", index) }