ZetCode

Go 排序

最后修改时间 2024 年 4 月 11 日

在本文中，我们将展示如何在 Golang 中对切片和用户定义的集合进行排序。

排序

排序是将元素按有序序列排列。在计算机科学中，已经开发了许多算法来对数据进行排序，包括归并排序、快速排序、选择排序或冒泡排序。（排序的另一个含义是分类；它是将具有相似属性的元素分组。）

排序的相反操作，即将元素序列重新排列成随机或无意义的顺序，称为洗牌。

基本数据类型可以按自然顺序排序，无论是字母顺序还是数字顺序。排序键指定用于执行排序的标准。我们还可以按多个键对对象进行排序。例如，在对用户进行排序时，用户的姓名可以用作主要排序键，他们的职业可以用作次要排序键。

排序顺序

标准顺序称为升序：A 到 Z，0 到 9。反向顺序称为降序：Z 到 A，9 到 0。对于日期和时间，升序意味着较早的值在前，较晚的值在后，例如 2019/1/1 会排在 2023/1/1 之前。

稳定排序

在稳定排序算法中，相等元素的初始顺序会得以保留。一些排序算法本身就是稳定的，而另一些则不是。例如，冒泡排序和归并排序是稳定的排序算法。另一方面，堆排序和快速排序是不稳定排序算法的示例。

考虑以下值：3715593。稳定排序会产生以下结果：1335579。值 3 和 5 的顺序得以保留。不稳定排序可能产生以下结果：1335579。

Go 排序

Go 提供了标准的 sort 包用于排序。排序函数会就地对数据进行排序。对于基本数据类型，我们有内置函数，例如 sort.Ints 和 sort.Strings。对于更复杂的类型，我们需要通过实现 sort.Interface 来创建自己的排序。

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

该接口包含三个函数：Len、Less 和 Swap。

Go 排序整数

sort.Ints 以升序对 int 切片进行排序。Reverse 函数返回数据的反向顺序。

sort_ints.go 
package main

import (
    "fmt"
    "sort"
)

func main() {

    vals := []int{3, 1, 0, 7, 2, 4, 8, 6}
    sort.Ints(vals)
    fmt.Println(vals)

    sort.Sort(sort.Reverse(sort.IntSlice(vals)))
    fmt.Println(vals)
}

该示例对整数切片进行升序和降序排序。

$ go run sort_ints.go
[0 1 2 3 4 6 7 8]
[8 7 6 4 3 2 1 0]

Go 排序字符串

sort.Strings 以升序对字符串切片进行排序。

sort_strings.go 
package main

import (
    "fmt"
    "sort"
)

func main() {

    words := []string{"bear", "atom", "world", "falcon", "cloud", "forest"}

    sort.Strings(words)
    fmt.Println(words)

    sort.Sort(sort.Reverse(sort.StringSlice(words)))
    fmt.Println(words)
}

我们有一个单词切片。我们将单词按升序和降序排序。

sort.Strings(words)

sort.Strings 按升序对单词进行排序。

sort.Sort(sort.Reverse(sort.StringSlice(words)))

借助 sort.Reverse 和 sort.StringSlice 函数，我们可以按降序对单词进行排序。

$ go run sort_strings.go
[atom bear cloud falcon forest world]
[world forest falcon cloud bear atom]

Go 排序带重音词

在下一个示例中，我们将对带重音的词进行排序。为此，我们使用 x/text 模块。

sort_accented_words.go 
package main

import (
    "fmt"

    "golang.org/x/text/collate"
    "golang.org/x/text/language"
)

func main() {

    words := []string{"čaj", "auto", "pot", "márny", "kľak", "chyba", "drevo",
        "cibuľa", "džíp", "džem", "šum", "pól", "čučoriedka", "banán", "čerešňa",
        "červený", "klam", "čierny", "tŕň", "pôst", "hôrny", "mat", "chobot",
        "cesnak", "kĺb", "mäta", "ďateľ", "troska", "sýkorka", "elektrón",
        "fuj", "zem", "guma", "hora", "gejzír", "ihla", "pýr", "hrozno",
        "jazva", "džavot", "lom"}

    c := collate.New(language.Slovak)
    c.SortStrings(words)

    fmt.Println(words)
}

我们有一个斯洛伐克语单词切片。

c := collate.New(language.Slovak)
c.SortStrings(words)

我们为斯洛伐克语创建一个排序规则，并使用 SortStrings 对单词进行排序。

$ go run sort_accented_words.go 
[auto banán cesnak cibuľa čaj čerešňa červený čierny čučoriedka ďateľ drevo
džavot džem džíp elektrón fuj gejzír guma hora hôrny hrozno chobot chyba ihla
jazva kľak klam kĺb lom márny mat mäta pól pot pôst pýr sýkorka šum tŕň troska
zem]

输出不是 100% 正确；但它是所有编程语言中最接近的解决方案之一。

Go 检查排序

我们可以使用 sort.StringsAreSorted、sort.IntsAreSorted 或 sort.SliceIsSorted 函数来检查数据是否已排序。

check_sorting.go 
package main

import (
    "fmt"
    "sort"
)

func main() {

    words := []string{"bear", "atom", "world", "falcon", "cloud", "forest"}

    sorted := sort.StringsAreSorted(words)
    fmt.Println(sorted)

    sort.Sort(sort.StringSlice(words))

    sorted = sort.StringsAreSorted(words)
    fmt.Println(sorted)

    // --------------------------------------------

    vals := []int{5, 2, 6, 3, 1, 7, 8, 4, 0}

    sorted = sort.IntsAreSorted(vals)
    fmt.Println(sorted)

    sort.Ints(vals)

    sorted = sort.IntsAreSorted(vals)
    fmt.Println(sorted)
}

在代码示例中，我们检查我们的两个切片是否已排序。

$ go run check_sorting.go
false
true
false
true

Go 自定义排序

对于自定义排序，我们需要实现 sort.Interface 函数。

custom_sorting.go 
package main

import (
    "fmt"
    "sort"
)

type ByLength []string

func (s ByLength) Len() int {
    return len(s)
}

func (s ByLength) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s ByLength) Less(i, j int) bool {
    return len(s[i]) < len(s[j])
}

func main() {
    words := []string{"cloud", "atom", "sea", "by", "forest", "maintenance"}
    sort.Sort(ByLength(words))
    fmt.Println(words)
}

在代码示例中，我们按长度对单词切片进行排序。

type ByLength []string

我们创建了一个自定义类型 ByLength，它是内置 []string 的别名。

func (s ByLength) Len() int {
    return len(s)
}

func (s ByLength) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s ByLength) Less(i, j int) bool {
    return len(s[i]) < len(s[j])
}

我们实现了排序接口所需的三个函数。

sort.Sort(ByLength(words))

我们将单词字符串切片转换为我们的类型，然后在该类型化的切片上调用 Sort 函数。

$ go run custom_sorting.go
[by sea atom cloud forest maintenance]

单词按长度升序排序。

Go sort.Slice

sort.Slice 是一个方便的函数，用于对切片中的数据进行排序，而无需创建自定义类型。

slice_fun.go 
package main

import (
    "fmt"
    "sort"
)

func main() {

    words := []string{"cloud", "atom", "sea", "by", "forest", "maintenance"}

    sort.Slice(words, func(i1, i2 int) bool {
        return len(words[i1]) < len(words[i2])
    })

    fmt.Println(words)

    sort.Slice(words, func(i1, i2 int) bool {
        return len(words[i1]) > len(words[i2])
    })

    fmt.Println(words)
}

我们按长度对单词切片进行排序。我们将一个匿名比较函数传递给 sort.Slice。

$ go run slice_fun.go
[by sea atom cloud forest maintenance]
[maintenance forest cloud atom sea by]

Go 按键对 map 进行排序

在以下示例中，我们将按键对 map 进行排序。

sort_map_keys.go 
package main

import (
    "fmt"
    "sort"
)

func main() {

    items := map[string]int{
        "coin":   12,
        "chair":  3,
        "pen":    4,
        "bottle": 9,
    }

    keys := make([]string, 0, len(items))

    for key := range items {
        keys = append(keys, key)
    }

    sort.Strings(keys)

    for _, key := range keys {
        fmt.Printf("%s %d\n", key, items[key])
    }
}

为了按键对 map 进行排序，我们将键提取到一个键切片中，对它们进行排序，最后使用这个排序后的切片提取值。

$ go run sort_map_keys.go
bottle 9
chair 3
coin 12
pen 4

Go 按值对 map 进行排序

在下一个示例中，我们将按值对 map 进行排序。该 map 存储了《圣经》中的单词及其频率。

$ wget https://raw.githubusercontent.com/janbodnar/data/main/the-king-james-bible.txt

我们使用《英王钦定本圣经》。

read_freq.go 
package main
import (
    "fmt"
    "io/ioutil"
    "log"
    "sort"
    "strings"
)

func main() {

    fileName := "the-king-james-bible.txt"

    bs, err := ioutil.ReadFile(fileName)

    if err != nil {

        log.Fatal(err)
    }

    text := string(bs)

    fields := strings.FieldsFunc(text, func(r rune) bool {

        return !('a' <= r && r <= 'z' || 'A' <= r && r <= 'Z' || r == '\'')
    })

    wordsCount := make(map[string]int)

    for _, field := range fields {

        wordsCount[field]++
    }

    keys := make([]string, 0, len(wordsCount))

    for key := range wordsCount {

        keys = append(keys, key)
    }

    sort.Slice(keys, func(i, j int) bool {

        return wordsCount[keys[i]] > wordsCount[keys[j]]
    })

    for idx, key := range keys {

        fmt.Printf("%s %d\n", key, wordsCount[key])

        if idx == 10 {
            break
        }
    }
}

我们统计《英王钦定本圣经》中单词的频率。

fields := strings.FieldsFunc(text, func(r rune) bool {

    return !('a' <= r && r <= 'z' || 'A' <= r && r <= 'Z' || r == '\'')
})

FieldsFunc 按非字母字符和撇号分割文本。这也将忽略所有诗句编号。

wordsCount := make(map[string]int)

for _, field := range fields {

    wordsCount[field]++
}

每个单词及其频率存储在 wordsCount 映射中。

keys := make([]string, 0, len(wordsCount))

for key := range wordsCount {

    keys = append(keys, key)
}

sort.Slice(keys, func(i, j int) bool {

    return wordsCount[keys[i]] > wordsCount[keys[j]]
})

为了按频率对单词进行排序，我们创建了一个新的 keys 切片。我们将所有单词放入其中，并按它们的频率值对它们进行排序。

for idx, key := range keys {

    fmt.Printf("%s %d\n", key, wordsCount[key])

    if idx == 10 {
        break
    }
}

我们打印圣经中出现频率最高的十个词。

$ go run word_freq.go
the 62103
and 38848
of 34478
to 13400
And 12846
that 12576
in 12331
shall 9760
he 9665
unto 8942
I 8854

Go 排序结构体

在以下示例中，我们将对结构体列表进行排序。

sort_struct.go 
package main

import (
    "fmt"
    "sort"
)

type Student struct {
    name  string
    score int
}

func main() {

    students := []Student{

        Student{name: "John", score: 45},
        Student{name: "Bill", score: 68},
        Student{name: "Sam", score: 98},
        Student{name: "Julia", score: 87},
        Student{name: "Tom", score: 91},
        Student{name: "Martin", score: 71},
    }

    sort.Slice(students, func(i, j int) bool {
        return students[i].score < students[j].score
    })

    fmt.Println(students)

    sort.Slice(students, func(i, j int) bool {
        return students[i].name > students[j].name
    })

    fmt.Println(students)
}

我们有一个从 Student 结构体创建的学生对象切片。我们将两个匿名函数提供给 sort.Slice，以按分数和姓名对切片进行排序。

$ go run sort_struct.go
[{John 45} {Bill 68} {Martin 71} {Julia 87} {Tom 91} {Sam 98}]
[{Tom 91} {Sam 98} {Martin 71} {Julia 87} {John 45} {Bill 68}]

Go 按多个字段排序

数据可以按多个标准进行排序。

sort_mul_fields.go 
package main

import (
    "fmt"
    "sort"
)

type Student struct {
    name  string
    score int
}

func main() {

    students := []Student{

        Student{name: "John", score: 87},
        Student{name: "Albert", score: 68},
        Student{name: "Bill", score: 68},
        Student{name: "Sam", score: 98},
        Student{name: "Xenia", score: 87},
        Student{name: "Lucia", score: 87},
        Student{name: "Tom", score: 91},
        Student{name: "Jane", score: 68},
        Student{name: "Martin", score: 71},
        Student{name: "Julia", score: 87},
    }

    sort.Slice(students, func(i, j int) bool {

        if students[i].score != students[j].score {
            return students[i].score < students[j].score
        }

        return students[i].name < students[j].name
    })

    fmt.Println(students)
}

在代码示例中，我们按分数对学生切片进行排序，当分数相同时，则按姓名排序。

sort.Slice(students, func(i, j int) bool {

    if students[i].score != students[j].score {
        return students[i].score < students[j].score
    }

    return students[i].name < students[j].name
})

排序逻辑在匿名函数中实现。首先，我们比较分数。然后，如果分数相同，我们比较姓名。

$ go run sort_mul_fields.go
[{Albert 68} {Bill 68} {Jane 68} {Martin 71} {John 87} {Julia 87}
    {Lucia 87} {Xenia 87} {Tom 91} {Sam 98}]

Go 按日期时间排序

在以下示例中，我们将按日期时间对数据进行排序。

sort_date_time.go 
package main

import (
    "fmt"
    "sort"
    "time"
)

type Purchase struct {
    id   string
    date time.Time
}

func main() {

    var purchases = make([]Purchase, 0)
    purchases = append(purchases, Purchase{id: "1", date: time.Now()})
    purchases = append(purchases, Purchase{id: "2", date: time.Now().AddDate(-3, 0, 7)})
    purchases = append(purchases, Purchase{id: "3", date: time.Now().AddDate(2, 4, 7)})
    purchases = append(purchases, Purchase{id: "4",
        date: time.Now().AddDate(-5, -5, -7)})

    sort.Slice(purchases, func(i, j int) bool {
        return purchases[i].date.Before(purchases[j].date)
    })

    for _, pur := range purchases {

        fmt.Printf("%s %s\n", pur.id, pur.date.Format("2 Jan 2006 15:04"))
    }
}

我们有一个购买记录切片。这些购买记录按其日期时间排序。

sort.Slice(purchases, func(i, j int) bool {
    return purchases[i].date.Before(purchases[j].date)
})

在比较函数中，我们使用 Before 函数来确定第一个时间是否早于第二个时间。

$ go run sort_date_time.go
4 13 May 2015 14:42
2 27 Oct 2017 14:42
1 20 Oct 2020 14:42
3 27 Feb 2023 14:42

来源

Go sort 包 - 参考

在本文中，我们对 Golang 中的数据进行了排序。

作者

我叫 Jan Bodnar，我是一名充满激情的程序员，拥有丰富的编程经验。我自 2007 年以来一直撰写编程文章。迄今为止，我已撰写了 1,400 多篇文章和 8 本电子书。我在编程教学方面拥有十多年的经验。

列出所有 Go 教程。