GO-深入理解Sort
Go 语言的 sort 包提供了对切片和用户自定义集合进行排序的功能。它的设计非常灵活，支持多种数据类型的排序，并且允许用户通过实现接口来自定义排序规则。以下是对 sort 包的深入解析，包括其核心接口、实现原理以及使用方法
核心接口
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
|
排序函数
sort.Sort
- 对实现了
sort.Interface 接口的类型进行排序
exmaple：
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func main() {
people := []Person{
{"Alice", 25},
{"Bob", 30},
{"Charlie", 20},
}
sort.Sort(ByAge(people))
fmt.Println(people)
}
|
sort.Slice
func Slice(slice interface{}, less func(i, j int) bool)
|
- 对任意切片进行排序，通过传入一个比较函数来定义排序规则
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
fmt.Println(nums)
}
|
sort.SliceStable
func SliceStable(slice interface{}, less func(i, j int) bool)
|
- 对任意切片进行稳定排序，通过传入一个比较函数来定义排序规则
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
func main() {
people := []Person{
{"Alice", 25},
{"Bob", 25},
{"Charlie", 30},
{"David", 20},
}
sort.SliceStable(people, func(i, j int) bool {
return people[i].Age < people[j].Age
})
fmt.Println(people)
}
|
sort.IsSorted
func IsSorted(data Interface) bool
|
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 2, 3, 4, 5}
fmt.Println(sort.IsSorted(sort.IntSlice(nums)))
}
|
排序原理
排序算法
- **
sort.Sort**：使用快速排序（QuickSort）的变体（内省排序）
- **
sort.Slice**：同样使用快速排序的变体（内省排序）
- **
sort.SliceStable**：使用归并排序（MergeSort）
内省排序（Introsort）
内省排序是快速排序、堆排序和插入排序的结合：
- 在大多数情况下，使用快速排序
- 当递归深度超过一定阈值时，切换到堆排序（避免快速排序的最坏情况）
- 对于小规模数据（如长度小于 12 的切片），使用插入排序
归并排序（MergeSort）
归并排序的核心是分治法：
- 将切片分成两部分
- 递归地对每一部分进行排序
- 将排序后的两部分合并
- 在合并过程中，如果两个元素相等，会优先保留左边部分的元素，从而保证排序的稳定性（所以不会改变原来的顺序）
自定义排序
- 通过实现
sort.Interface 接口，可以对任意类型进行排序
package main
import (
"fmt"
"sort"
)
type ByLength []string
func (s ByLength) Len() int { return len(s) }
func (s ByLength) Less(i, j int) bool { return len(s[i]) < len(s[j]) }
func (s ByLength) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func main() {
fruits := []string{"peach", "banana", "kiwi"}
sort.Sort(ByLength(fruits))
fmt.Println(fruits)
}
|
预定义类型
sort 包为一些常见类型提供了预定义的排序实现：
sort.IntSlice：对 []int 排序。sort.Float64Slice：对 []float64 排序。sort.StringSlice：对 []string 排序
排序性能对比
| 特性 |
sort.Slice（快速排序） |
sort.SliceStable（归并排序） |
| 时间复杂度 |
平均 O(n log n)，最坏 O(n^2) |
始终 O(n log n) |
| 空间复杂度 |
O(log n)（递归栈） |
O(n)（额外空间） |
| 稳定性 |
不稳定 |
稳定 |
| 适用场景 |
不需要稳定性的场景 |
需要稳定性的场景 |
alipay
