Go 并发编程 - 第 38 课：排序与搜索 sort

1. 学习目标

通过本课学习，你将能够：

掌握 Go 标准库 sort 包的基本功能和使用方法
学会对各种类型的切片进行排序（整数、字符串、结构体等）
理解并使用自定义排序规则（通过函数或实现 sort.Interface）
掌握使用 sort.Search 进行高效二分查找的技巧
了解排序稳定性及其应用场景

2. 核心概念

sort 包提供了高效的切片排序功能。它支持基本数据类型的排序，也允许通过自定义规则排序。

关键概念：

sort.Slice() - 最常用的排序函数，接受一个切片和一个比较函数
sort.Sort() - 需要实现 sort.Interface 接口（三个方法：Len、Less、Swap）
sort.Search() - 二分查找，用于在有序切片中快速查找元素
排序稳定性 - 相等元素的相对顺序在排序后保持不变

sort.Interface 接口定义如下：

type Interface interface {
    Len() int           // 返回元素数量
    Less(i, j int) bool // 比较元素i和j，如果i<j返回true
    Swap(i, j int)      // 交换元素i和j
}

3. 代码示例

3.1 基本类型排序

package main

import (
    "fmt"
    "sort"
)

func main() {
    // 整数切片排序
    numbers := []int{64, 25, 12, 22, 11}
    fmt.Println("排序前:", numbers)
    
    sort.Ints(numbers) // 升序排序
    fmt.Println("升序排序后:", numbers)
    
    sort.Sort(sort.Reverse(sort.IntSlice(numbers))) // 降序排序
    fmt.Println("降序排序后:", numbers)
    
    // 字符串切片排序
    fruits := []string{"香蕉", "苹果", "橙子", "猕猴桃"}
    fmt.Println("\n排序前:", fruits)
    
    sort.Strings(fruits)
    fmt.Println("字符串排序后:", fruits)
    
    // 浮点数排序
    floats := []float64{3.14, 1.41, 2.72, 1.73}
    fmt.Println("\n浮点数排序前:", floats)
    
    sort.Float64s(floats)
    fmt.Println("浮点数排序后:", floats)
}

3.2 自定义排序

package main

import (
    "fmt"
    "sort"
)

// 定义学生结构体
type Student struct {
    Name string
    Age  int
    Grade float64
}

func main() {
    students := []Student{
        {"张三", 20, 85.5},
        {"李四", 19, 92.3},
        {"王五", 21, 78.9},
        {"赵六", 20, 88.0},
    }
    
    fmt.Println("原始顺序:", students)
    
    // 方法1: 使用sort.Slice自定义排序（按年龄升序）
    sort.Slice(students, func(i, j int) bool {
        return students[i].Age < students[j].Age
    })
    fmt.Println("按年龄升序:", students)
    
    // 方法2: 按成绩降序排序
    sort.Slice(students, func(i, j int) bool {
        return students[i].Grade > students[j].Grade
    })
    fmt.Println("按成绩降序:", students)
    
    // 方法3: 多字段排序（先按年龄，再按成绩）
    sort.Slice(students, func(i, j int) bool {
        if students[i].Age != students[j].Age {
            return students[i].Age < students[j].Age
        }
        return students[i].Grade > students[j].Grade
    })
    fmt.Println("多字段排序:", students)
}

3.3 实现 sort.Interface

package main

import (
    "fmt"
    "sort"
)

// 员工结构体
type Employee struct {
    ID    int
    Name  string
    Salary float64
}

// 为员工切片实现sort.Interface
type Employees []Employee

func (e Employees) Len() int {
    return len(e)
}

func (e Employees) Less(i, j int) bool {
    // 先按工资降序，再按ID升序
    if e[i].Salary != e[j].Salary {
        return e[i].Salary > e[j].Salary
    }
    return e[i].ID < e[j].ID
}

func (e Employees) Swap(i, j int) {
    e[i], e[j] = e[j], e[i]
}

func main() {
    employees := Employees{
        {1, "张三", 8500},
        {2, "李四", 12000},
        {3, "王五", 9500},
        {4, "赵六", 12000},
        {5, "钱七", 7800},
    }
    
    fmt.Println("排序前:")
    for _, emp := range employees {
        fmt.Printf("ID:%d Name:%s Salary:%.2f\n", emp.ID, emp.Name, emp.Salary)
    }
    
    sort.Sort(employees)
    
    fmt.Println("\n排序后:")
    for _, emp := range employees {
        fmt.Printf("ID:%d Name:%s Salary:%.2f\n", emp.ID, emp.Name, emp.Salary)
    }
}

3.4 二分查找

package main

import (
    "fmt"
    "sort"
)

func main() {
    // 注意：二分查找必须基于有序切片
    numbers := []int{10, 20, 30, 40, 50, 60, 70, 80, 90}
    fmt.Println("有序切片:", numbers)
    
    // 查找特定值
    target := 40
    index := sort.SearchInts(numbers, target)
    if index < len(numbers) && numbers[index] == target {
        fmt.Printf("找到 %d，索引为 %d\n", target, index)
    } else {
        fmt.Printf("%d 未找到\n", target)
    }
    
    // 查找插入位置（第一个大于等于target的位置）
    target = 35
    index = sort.Search(len(numbers), func(i int) bool {
        return numbers[i] >= target
    })
    fmt.Printf("第一个大于等于 %d 的位置是索引 %d\n", target, index)
    
    // 使用Search实现自定义查找
    // 假设我们有降序排序的切片，查找第一个小于等于target的位置
    descNumbers := []int{90, 80, 70, 60, 50, 40, 30, 20, 10}
    target = 45
    index = sort.Search(len(descNumbers), func(i int) bool {
        return descNumbers[i] <= target
    })
    fmt.Printf("降序切片中第一个小于等于 %d 的位置是索引 %d\n", target, index)
}

4. 实践练习

练习1：基本排序操作

创建一个整数切片 [5, 2, 8, 1, 9, 3, 7, 4, 6]，完成以下任务：

升序排序并输出
降序排序并输出
查找数字 4 的索引位置

练习2：自定义排序

创建一个包含以下信息的结构体切片：

type Book struct {
    Title  string
    Author string
    Price  float64
    Pages  int
}

书籍数据：

《Go语言高级编程》- 柴树杉 - 79.0 - 560页
《Go并发编程实战》- 郝林 - 89.0 - 420页
《Go语言实战》- William Kennedy - 59.0 - 380页
《Go Web编程》- 谢孟军 - 69.0 - 480页

实现以下排序：

按价格升序排序
按页数降序排序
先按作者姓氏长度升序，再按书名长度升序

练习3：二分查找应用

给定一个已排序的整数切片 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，编写一个函数：

查找数字 8 的插入位置（使切片仍保持有序）
查找数字 11 是否存在
扩展：实现一个函数，接受切片和目标值，返回目标值应该插入的位置，无论切片是否已排序（如果未排序则先排序）

5. 常见错误

对未排序的切片使用二分查找

// 错误示例
nums := []int{5, 3, 1, 4, 2}
idx := sort.SearchInts(nums, 4) // 结果不确定

排序函数使用不当

// 错误：sort.Slice要求返回值严格为bool
sort.Slice(nums, func(i, j int) bool {
    return nums[i] - nums[j] // 错误，应该返回nums[i] < nums[j]
})

忽略排序稳定性

// 当需要保持相等元素原始顺序时，应使用SliceStable
// sort.Slice可能不稳定，sort.SliceStable稳定

自定义比较函数逻辑错误

// 常见错误：混淆升序和降序逻辑
// 升序：return a < b
// 降序：return a > b

忽略边界情况

// 使用二分查找前应检查切片长度是否为0
if len(slice) == 0 {
    return 0 // 空切片的插入位置始终为0
}

6. 小结

sort 包提供了高效的切片排序和查找功能
sort.Ints、sort.Strings、sort.Float64s 用于基本类型的快速排序
sort.Slice 通过传入比较函数实现灵活的自定义排序
sort.Sort 需要实现 sort.Interface 接口，适用于复杂的排序需求
sort.Search 和 sort.SearchInts 用于在有序切片中快速查找元素
排序稳定性在某些场景下很重要，使用 sort.SliceStable 保持稳定
二分查找要求切片必须是有序的，时间复杂度为 O(log n)

记住：在使用排序前，考虑清楚排序规则和是否需要稳定性；在使用查找前，确保数据是有序的！

排序与搜索 sort