对int, float64, string列表进行排序

可以直接使用库函数, 进行升序排序, 目前有以下三个库函数sort.Ints,sort.Strings,sort.Float64s

1
2
3

a := []int{1, 5, 4, 3, 2}
sort.Ints(a)
fmt.Println(a)

使用自定义比较器

从go1.8后，可以直接使用sort.Slice, 使用自定义的比较函数less(i, j int) bool. 如果想稳定排序，可以使用sort.SliceStable

sort.Slice内部使用的接口和反射来实现的，效率上面会打一定的折扣。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

package main

import (
        "fmt"
        "sort"
)

type User struct {
        Name string
        Age  int
}

func main() {
        users := []User{
                User{"test", 12},
                User{"james", 32},
                User{"bob", 18},
                User{"alice", 16},
        }

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

        fmt.Println(users)
}

实现排序接口

  1. 使用sort.Sort和sort.Stable函数

  2. 只要实现了sort.Interface接口的集合，都可以通过上面的两个函数进行排序。

    1
2
3
4
5
6
7
8
9

    type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

    package main

import (
    "fmt"
    "sort"
)

type User struct {
    Name string
    Age  int
}

type ByAge []User

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() {
    users := []User{
            User{"test", 12},
            User{"james", 32},
            User{"bob", 18},
            User{"alice", 16},
    }

    sort.Sort(ByAge(users))
    fmt.Println(users)
}

性能对比

Slice vs Sorting Type (of Slice) with Sort implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

package main

import (
        "sort"
        "testing"
)

type User struct {
        Name string
        Age  int
}

var TestCases = []User{
        {"alice", 9},
        {"james", 35},
        {"wade", 15},
        {"test", 51},
        {"beyond", 25},
        {"brand", 59},
        {"bob", 10},
        {"twitter", 15},
        {"google", 22},
        {"facebook", 91},
}

// Example One - Sorting Slice Directly
// somehow - slowest way to sort it.
func SortSlice(users []User) {
        sort.Slice(users, func(i, j int) bool {
                return users[i].Name < users[j].Name
        })
}

func BenchmarkSlice(b *testing.B) {
        tmp := make([]User, len(TestCases))
        for i := 0; i < b.N; i++ {
                copy(tmp, TestCases)
                SortSlice(tmp)
        }
}

// Example Two - Sorting Slice Directly
// much faster performance
type ByName []User

// Sort interface implementation
func (n ByName) Less(i, j int) bool { return n[i].Name < n[j].Name }
func (n ByName) Len() int           { return len(n) }
func (n ByName) Swap(i, j int)      { n[i], n[j] = n[j], n[i] }

func SortStruct(users []User) {
        sort.Sort(ByName(users))
}

func BenchmarkStruct(b *testing.B) {
        tmp := make([]User, len(TestCases))
        for i := 0; i < b.N; i++ {
                copy(tmp, TestCases)
                SortStruct(tmp)
        }
}

测试结果:

1
2
3
4
5
6
7
8

$ go test -bench=.
goos: linux
goarch: amd64
pkg: hello
BenchmarkSlice-2         2000000               976 ns/op
BenchmarkStruct-2        3000000               401 ns/op
PASS
ok      hello   4.564s

参考

  1. The 3 ways to sort in Go