go sort

Go 提供了内置的 sort 包来实现各种排序算法。它支持对不同数据结构（如切片、数组和自定义类型）进行排序。以下是对 Go sort 方法的详细介绍和用法示例：

---

1. 基本排序方法

Go 的 sort 包提供了以下几种常见的排序方法：

• sort.Ints()
• sort.Float64s()
• sort.Strings()
• sort.Sort()

2. 对切片排序

Go 的 sort 包可以对切片进行排序。常用的排序方法如下：

(1) sort.Ints() - 排序整数切片

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{3, 1, 4, 5, 2}
    sort.Ints(arr) // 对整数切片排序
    fmt.Println(arr) // 输出: [1 2 3 4 5]
}

(2) sort.Float64s() - 排序浮点数切片

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []float64{3.14, 2.71, 1.61, 1.41}
    sort.Float64s(arr) // 对浮点数切片排序
    fmt.Println(arr)   // 输出: [1.41 1.61 2.71 3.14]
}

(3) sort.Strings() - 排序字符串切片

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []string{"banana", "apple", "cherry"}
    sort.Strings(arr) // 对字符串切片排序
    fmt.Println(arr)  // 输出: [apple banana cherry]
}

3. 对自定义数据类型排序

如果需要对自定义的数据类型进行排序，需要实现 sort.Interface 接口，这个接口包含三个方法：

• Len() int：返回元素的数量。
• Less(i, j int) bool：比较元素 i 和 j，返回 true 表示 i 排在前面。
• Swap(i, j int)：交换元素 i 和 j。

示例：排序自定义结构体切片

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", 30},
        {"Bob", 25},
        {"Charlie", 35},
    }

    // 使用自定义排序
    sort.Sort(ByAge(people))
    fmt.Println(people) // 输出: [{Bob 25} {Alice 30} {Charlie 35}]
}

4. 逆序排序

如果需要对切片进行逆序排序，可以使用 sort.Sort() 和自定义的 Less() 方法。

示例：逆序排序

package main

import (
    "fmt"
    "sort"
)

type ByDesc []int

func (a ByDesc) Len() int {
    return len(a)
}

func (a ByDesc) Less(i, j int) bool {
    return a[i] > a[j] // 按降序排列
}

func (a ByDesc) Swap(i, j int) {
    a[i], a[j] = a[j], a[i]
}

func main() {
    arr := []int{3, 1, 4, 5, 2}
    sort.Sort(ByDesc(arr)) // 使用自定义排序规则
    fmt.Println(arr)       // 输出: [5 4 3 2 1]
}

5. 使用 sort.Reverse 进行逆序排序

Go 还提供了 sort.Reverse() 方法，可以将已有的排序规则进行反转（逆序排序）。

示例：使用 sort.Reverse 逆序排序

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{3, 1, 4, 5, 2}
    sort.Sort(sort.Reverse(sort.IntSlice(arr))) // 使用 sort.Reverse 反转排序
    fmt.Println(arr) // 输出: [5 4 3 2 1]
}

---

6. 排序算法复杂度

Go 的 sort 包使用 快速排序（Quicksort）作为默认排序算法，最坏情况下的时间复杂度为 O(n²)，但平均情况下为 O(n log n)。

对于稳定的排序（如在相同元素排序时保持它们的相对位置），sort 包并不提供内建的稳定排序方式，但可以通过自定义实现来完成。

7. 总结

• 常用排序方法：sort.Ints()、sort.Float64s()、sort.Strings()。
• 自定义排序：实现 sort.Interface 接口（Len()、Less()、Swap()）。
• 逆序排序：使用 sort.Reverse() 或自定义 Less() 方法。
• 算法复杂度：快速排序，平均复杂度为 O(n log n)，最坏为 O(n²)。

使用 Go 的 sort 包，可以方便地对各种类型的数据进行高效的排序。