排序（sort包）

使用 sort.Interface 來排序

排序是一個在很多程序中廣泛使用的操作。sort 包提供了針對任意序列根據任意排序函數原地排序的功能。
這樣的設計號稱并不常見。在很多語言中，排序算法跟序列數據類型綁定，排序函數跟序列元素類型綁定。但 Go 語言的 sort.Sort 函數對序列和其中元素的布局無任何要求，它使用 sort.Interface 接口來實現。

接口實現

一個原地排序算法需要知道三個信息：

1. 序列長度
2. 比較兩個元素的含義
3. 如何交換兩個元素

所以 sort.Interface 接口就有三個方法：

package sort

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

字符串排序

要對序列排序，需要先確定一個實現了上面三個方法的類型，接著把 sort.Sort 函數應用到上面這類方法的示例上。以字符串切片 []string 為例，定義一個新的類型 StringSlice 以及它的三個方法如下：

type StringSlice []string

func (p StringSlice) Len() int           { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

現在要對一個字符串切片進行排序，先把類型轉換為 StringSlice 類型，然后調用 sort.Sort 函數即可：

sort.Sort(StringSlice(names))

字符串切片的排序太常見了，所以 sort 包提供了 StringSLice 類型，以及一個直接排序的 Strings 函數。上面對 StringSlice 類型及其方法的定義就是源碼里實現的代碼。所以要對字符串切片進行排序，直接調用 srot.Strings 函數即可：

sort.Strings(names)

為了簡便，sort 包專門對 []int、[]string、[]float64 這三個類型提供了排序的函數和相關類型。對于其他類型，就需要自己寫了，不過寫起來也不復雜。

反轉 Reverse

sort.Reverse 函數值得仔細看一下，它使用了一個重要的概念組合。sort 包定義了一個 reverse 類型，這個類型是一個嵌入了 sort.Interface 的結構。reverse 的 Less 方法，直接調用內嵌的 sort.Interface 值的 Less 方法，但是調換了下標，這樣就實現了顛倒排序的結果了：

package sort

type reverse struct { Interface } // 這個是在sort包里的，所以就是 sort.Interface
func (r reverse) Less(i, j int) bool { return r.Interface.Less(j, i) }  // 這里調換了函數體中 i 和 j 的位置
func Reverse(data Interface) Interface { return &reverse{data} }

reverse 的另外兩個方法 Len 和 Swap，沒有定義，就會由內嵌的 sort.Interface 隱式提供。導出函數 Reverse 則返回一個包含原始的 sort.Interface 值的 reverse 實例。最終反轉排序的調用如下，先做類型轉換，然后加一步通過 Reverse 函數生成 reverse 實例，最后就是調用 sort.Sort 函數完成排序：

sort.Sort(sort.Reverse(StringSlice(names)))

復雜類型的排序

對于一個復雜的類型，比如結構體，它會有多個字段，也就是可能需要對多個維度進行排序。

數據和結構

下面是一個復雜的結構體類型，并且數據也已經準備好了：

type Track struct {
    Title  string
    Artist string
    Album  string
    Year   int
    Length time.Duration
}

var tracks = []*Track{
    {"Go", "Delilah", "From the Roots Up", 2012, length("3m38s")},
    {"Go", "Moby", "Moby", 1992, length("3m37s")},
    {"Go Ahead", "Alicia Keys", "As I Am", 2007, length("4m36s")},
    {"Ready 2 Go", "Martin Solveig", "Smash", 2011, length("4m24s")},
}

func length(s string) time.Duration {
    d, err := time.ParseDuration(s)
    if err != nil {
        panic(s)
    }
    return d
}

用表格輸出結構體

這里使用 text/tabwriter 包可以生成一個干凈整潔的表格。這里注意，*tabwriter.Writer 滿足 io.Writer 接口，先用它收集所有寫入的數據，在 Flush 方法調用時才會格式化整個表格并且輸出：

func printTracks(tracks []*Track) {
    const format = "%v\t%v\t%v\t%v\t%v\t\n"
    tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0)
    fmt.Fprintf(tw, format, "Title", "Artist", "Album", "Year", "Length")
    fmt.Fprintf(tw, format, "-----", "------", "-----", "----", "------")
    for _, t := range tracks {
        fmt.Fprintf(tw, format, t.Title, t.Artist, t.Album, t.Year, t.Length)
    }
    tw.Flush()
}

排序

按照 Artist 字段進行排序：

type byArtist []*Track

func (x byArtist) Len() int           { return len(x) }
func (x byArtist) Less(i, j int) bool { return x[i].Artist < x[j].Artist }
func (x byArtist) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

按照 Year 字段進行排序：

type byYear []*Track

func (x byYear) Len() int           { return len(x) }
func (x byYear) Less(i, j int) bool { return x[i].Year < x[j].Year }
func (x byYear) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

優化

上面分別對2個字段定義了排序。像這樣，對于每一個排序都需要實現一個新的 sort.Interface。但是其實只有 Less 方法不同，而 Len 和 Swap 方法都是一樣的。
在下面的例子中，具體類型 customSort 組合了一個要排序的切片類型和一個函數，這樣每次只要寫一個比較函數就可以定義一個新的排序。從這個例子也可以看到，實現 sort.Interface 的具體類型并不一定都是切片，比如這里的 customSort 就是一個結構體：

type customSort struct {
    t    []*Track
    less func(x, y *Track) bool
}

func (x customSort) Len() int           { return len(x.t) }
func (x customSort) Less(i, j int) bool { return x.less(x.t[i], x.t[j]) }
func (x customSort) Swap(i, j int)      { x.t[i], x.t[j] = x.t[j], x.t[i] }

接下來就定義一個多層的比較函數，先對 Title 排序，然后對 Year，最后是時長：

sort.Sort(customSort{tracks, func(x, y *Track) bool {
    if x.Title != y.Title {
        return x.Title < y.Title
    }
    if x.Year != y.Year {
        return x.Year < y.Year
    }
    if x.Length != y.Length {
        return x.Length < y.Length
    }
    return false
}})

檢查是否有序

一個長度為 n 的序列進行排序需要 O(n logn) 次比較操作，而判斷一個序列是否已經排好序值需要最多 (n-1) 次比較。sort 包提供的 IsSorted 函數可以判斷序列是否是排好序的。

values := []int{3, 1, 4, 1}
fmt.Println(sort.IntsAreSorted(values))                         // "false"
sort.Ints(values)                                               // 排序
fmt.Println(values)                                             // "[1 1 3 4]"
fmt.Println(sort.IntsAreSorted(values))                         // "true"
sort.Sort(sort.Reverse(sort.IntSlice(values)))                  // 反轉
fmt.Println(values)                                             // "[4 3 1 1]"
fmt.Println(sort.IntsAreSorted(values))                         // "false"
fmt.Println(sort.IsSorted(sort.Reverse(sort.IntSlice(values)))) // "true"

完整示例代碼

上面的代碼的源碼文件，可以運行：

package main

import (
    "fmt"
    "os"
    "sort"
    "text/tabwriter"
    "time"
)

type Track struct {
    Title  string
    Artist string
    Album  string
    Year   int
    Length time.Duration
}

var tracks = []*Track{
    {"Go", "Delilah", "From the Roots Up", 2012, length("3m38s")},
    {"Go", "Moby", "Moby", 1992, length("3m37s")},
    {"Go Ahead", "Alicia Keys", "As I Am", 2007, length("4m36s")},
    {"Ready 2 Go", "Martin Solveig", "Smash", 2011, length("4m24s")},
}

func length(s string) time.Duration {
    d, err := time.ParseDuration(s)
    if err != nil {
        panic(s)
    }
    return d
}

func printTracks(tracks []*Track) {
    const format = "%v\t%v\t%v\t%v\t%v\t\n"
    tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0)
    fmt.Fprintf(tw, format, "Title", "Artist", "Album", "Year", "Length")
    fmt.Fprintf(tw, format, "-----", "------", "-----", "----", "------")
    for _, t := range tracks {
        fmt.Fprintf(tw, format, t.Title, t.Artist, t.Album, t.Year, t.Length)
    }
    tw.Flush()
}

type byArtist []*Track

func (x byArtist) Len() int           { return len(x) }
func (x byArtist) Less(i, j int) bool { return x[i].Artist < x[j].Artist }
func (x byArtist) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

type byYear []*Track

func (x byYear) Len() int           { return len(x) }
func (x byYear) Less(i, j int) bool { return x[i].Year < x[j].Year }
func (x byYear) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

func main() {
    fmt.Println("byArtist:")
    sort.Sort(byArtist(tracks))
    printTracks(tracks)

    fmt.Println("\nReverse(byArtist):")
    sort.Sort(sort.Reverse(byArtist(tracks)))
    printTracks(tracks)

    fmt.Println("\nbyYear:")
    sort.Sort(byYear(tracks))
    printTracks(tracks)

    fmt.Println("\nCustom:")
    sort.Sort(customSort{tracks, func(x, y *Track) bool {
        if x.Title != y.Title {
            return x.Title < y.Title
        }
        if x.Year != y.Year {
            return x.Year < y.Year
        }
        if x.Length != y.Length {
            return x.Length < y.Length
        }
        return false
    }})
    printTracks(tracks)
}

type customSort struct {
    t    []*Track
    less func(x, y *Track) bool
}

func (x customSort) Len() int           { return len(x.t) }
func (x customSort) Less(i, j int) bool { return x.less(x.t[i], x.t[j]) }
func (x customSort) Swap(i, j int)      { x.t[i], x.t[j] = x.t[j], x.t[i] }

func init() {
    values := []int{3, 1, 4, 1}
    fmt.Println(sort.IntsAreSorted(values))                         // "false"
    sort.Ints(values)                                               // 排序
    fmt.Println(values)                                             // "[1 1 3 4]"
    fmt.Println(sort.IntsAreSorted(values))                         // "true"
    sort.Sort(sort.Reverse(sort.IntSlice(values)))                  // 反轉
    fmt.Println(values)                                             // "[4 3 1 1]"
    fmt.Println(sort.IntsAreSorted(values))                         // "false"
    fmt.Println(sort.IsSorted(sort.Reverse(sort.IntSlice(values)))) // "true"
}

穩定的排序

sort.Sort 是不穩定的排序。在“優化”章節里的例子，先對Title進行比較，然后是Year，再是Length，實現了多個字段的排序。在第一關鍵字相等的情況下，再通過第二關鍵字進行比較。整個過程只進行了一次序列的交換，這樣看不出問題。
如果對多個關鍵字進行排序，但是不是像上面這樣通過一次比較交換完成，而是先對一個關鍵字進行排序，得到一個已經有序的序列。然后再在這個序列的基礎上，再進行一次對另一個關鍵字的排序，穩定的排序和不穩定的排序的結果就會有差別。比如排序第一關鍵字是年齡，第二關鍵字是姓名。那么先做一個姓名的排序（穩定不穩定無所謂），然后再在原來的基礎上做一次年齡的排序（必須穩定），才能得到正確的結果。下面通過具體事例來說明，穩定排序和不穩定排序的差別。

準備數據

數據結構、打印的函數、具體數據如下代碼實現：

type Student struct {
    name string
    age  int
}

var students []*Student

func printStudents(students []*Student) {
    const format = "%v\t%v\t\n"
    tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0)
    fmt.Fprintf(tw, format, "name", "age")
    fmt.Fprintf(tw, format, "----", "---")
    for _, s := range students {
        fmt.Fprintf(tw, format, s.name, s.age)
    }
    tw.Flush()
}

func init() {
    students = []*Student{
        &Student{"Adam", 20},
        &Student{"Bob", 18},
        &Student{"Clark", 19},
        &Student{"Daisy", 18},
        &Student{"Eva", 20},
        &Student{"Frank", 20},
        &Student{"Gideon", 19},
    }
}

接口實現

這里使用通用的 less 方法：

type studentSort struct {
    s    []*Student
    less func(x, y *Student) bool
}

func (x studentSort) Len() int           { return len(x.s) }
func (x studentSort) Less(i, j int) bool { return x.less(x.s[i], x.s[j]) }
func (x studentSort) Swap(i, j int)      { x.s[i], x.s[j] = x.s[j], x.s[i] }

不穩定的排序

先對 name 進行排序，然后再原來序列的基礎上對 age 進行排序：

func main() {
    sort.Sort(studentSort{students, func(x, y *Student) bool {
        if x.name != y.name {
            return x.name < y.name
        }
        return false
    }})

    sort.Sort(studentSort{students, func(x, y *Student) bool {
        if x.age != y.age {
            return x.age < y.age
        }
        return false
    }})
    printStudents(students)
}

最后打印的結果是這樣的：

PS H:\Go\src\gopl\output\sort\stable> go run main.go
name    age
----    ---
Bob     18
Daisy   18
Gideon  19
Clark   19
Eva     20
Frank   20
Adam    20
PS H:\Go\src\gopl\output\sort\stable>

在這個結果里年齡相同的數據，并沒有按字母順序排序，雖然之前已經按字母順序進行了排序，不過在第二次排序的時候，會把之前的順序打亂，這就是不穩定的排序。

穩定的排序

這里來看看穩定的排序。這里只要把 sort.Sort 函數替換成 sort.Stable 即可：

func main() {
    sort.Sort(studentSort{students, func(x, y *Student) bool {
        if x.name != y.name {
            return x.name < y.name
        }
        return false
    }})

    sort.Stable(studentSort{students, func(x, y *Student) bool {
        if x.age != y.age {
            return x.age < y.age
        }
        return false
    }})
    printStudents(students)
}

這里只替換了第二次排序的函數。第一次排序的時候假設序列本來就是亂的，所以這里并沒有需要穩定的必要。
這次再來看下結果：

PS H:\Go\src\gopl\output\sort\stable> go run main.go
name    age
----    ---
Bob     18
Daisy   18
Clark   19
Gideon  19
Adam    20
Eva     20
Frank   20
PS H:\Go\src\gopl\output\sort\stable>

這次的結果是期望的樣子了，按年齡排序，如果年齡相同，再按字母順序排序。

小結

sort.Stable 雖然能保證排序的穩定性，但是犧牲了效率。如果需要保證序列的穩定性，那么就要用 sort.Stable 函數來代替 sort.Sort。
但是如果僅僅只是要對多個字段進行排序，也可以直接在比較的時候就完成全部字段的比較，僅做一次序列的調換（就是排序）。就向上面“優化”章節里的 customSort 實現的那樣，下面是這里例子里的實現：

func main() {
    sort.Sort(studentSort{students, func(x, y *Student) bool {
        if x.age != y.age {
            return x.age < y.age
        }
        if x.name != y.name {
            return x.name < y.name
        }
        return false
    }})
    printStudents(students)
}