排序是一個(gè)在很多程序中廣泛使用的操作。sort 包提供了針對(duì)任意序列根據(jù)任意排序函數(shù)原地排序的功能。
這樣的設(shè)計(jì)號(hào)稱并不常見。在很多語言中，排序算法跟序列數(shù)據(jù)類型綁定，排序函數(shù)跟序列元素類型綁定。但 Go 語言的 sort.Sort 函數(shù)對(duì)序列和其中元素的布局無任何要求，它使用 sort.Interface 接口來實(shí)現(xiàn)。
一個(gè)原地排序算法需要知道三個(gè)信息：
所以 sort.Interface 接口就有三個(gè)方法：
重慶分公司
重慶分公司
package sort
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}要對(duì)序列排序，需要先確定一個(gè)實(shí)現(xiàn)了上面三個(gè)方法的類型，接著把 sort.Sort 函數(shù)應(yīng)用到上面這類方法的示例上。以字符串切片 []string 為例，定義一個(gè)新的類型 StringSlice 以及它的三個(gè)方法如下：
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] }現(xiàn)在要對(duì)一個(gè)字符串切片進(jìn)行排序，先把類型轉(zhuǎn)換為 StringSlice 類型，然后調(diào)用 sort.Sort 函數(shù)即可：
sort.Sort(StringSlice(names))字符串切片的排序太常見了，所以 sort 包提供了 StringSLice 類型，以及一個(gè)直接排序的 Strings 函數(shù)。上面對(duì) StringSlice 類型及其方法的定義就是源碼里實(shí)現(xiàn)的代碼。所以要對(duì)字符串切片進(jìn)行排序，直接調(diào)用 srot.Strings 函數(shù)即可：
sort.Strings(names)為了簡便，sort 包專門對(duì) []int、[]string、[]float64 這三個(gè)類型提供了排序的函數(shù)和相關(guān)類型。對(duì)于其他類型，就需要自己寫了，不過寫起來也不復(fù)雜。
sort.Reverse 函數(shù)值得仔細(xì)看一下，它使用了一個(gè)重要的概念組合。sort 包定義了一個(gè) reverse 類型，這個(gè)類型是一個(gè)嵌入了 sort.Interface 的結(jié)構(gòu)。reverse 的 Less 方法，直接調(diào)用內(nèi)嵌的 sort.Interface 值的 Less 方法，但是調(diào)換了下標(biāo)，這樣就實(shí)現(xiàn)了顛倒排序的結(jié)果了：
package sort
type reverse struct { Interface } // 這個(gè)是在sort包里的，所以就是 sort.Interface
func (r reverse) Less(i, j int) bool { return r.Interface.Less(j, i) } // 這里調(diào)換了函數(shù)體中 i 和 j 的位置
func Reverse(data Interface) Interface { return &reverse{data} }reverse 的另外兩個(gè)方法 Len 和 Swap，沒有定義，就會(huì)由內(nèi)嵌的 sort.Interface 隱式提供。導(dǎo)出函數(shù) Reverse 則返回一個(gè)包含原始的 sort.Interface 值的 reverse 實(shí)例。最終反轉(zhuǎn)排序的調(diào)用如下，先做類型轉(zhuǎn)換，然后加一步通過 Reverse 函數(shù)生成 reverse 實(shí)例，最后就是調(diào)用 sort.Sort 函數(shù)完成排序：
sort.Sort(sort.Reverse(StringSlice(names)))對(duì)于一個(gè)復(fù)雜的類型，比如結(jié)構(gòu)體，它會(huì)有多個(gè)字段，也就是可能需要對(duì)多個(gè)維度進(jìn)行排序。
下面是一個(gè)復(fù)雜的結(jié)構(gòu)體類型，并且數(shù)據(jù)也已經(jīng)準(zhǔn)備好了：
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 包可以生成一個(gè)干凈整潔的表格。這里注意，*tabwriter.Writer 滿足 io.Writer 接口，先用它收集所有寫入的數(shù)據(jù)，在 Flush 方法調(diào)用時(shí)才會(huì)格式化整個(gè)表格并且輸出：
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 字段進(jìn)行排序：
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 字段進(jìn)行排序：
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] }上面分別對(duì)2個(gè)字段定義了排序。像這樣，對(duì)于每一個(gè)排序都需要實(shí)現(xiàn)一個(gè)新的 sort.Interface。但是其實(shí)只有 Less 方法不同，而 Len 和 Swap 方法都是一樣的。
在下面的例子中，具體類型 customSort 組合了一個(gè)要排序的切片類型和一個(gè)函數(shù)，這樣每次只要寫一個(gè)比較函數(shù)就可以定義一個(gè)新的排序。從這個(gè)例子也可以看到，實(shí)現(xiàn) sort.Interface 的具體類型并不一定都是切片，比如這里的 customSort 就是一個(gè)結(jié)構(gòu)體：
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] }接下來就定義一個(gè)多層的比較函數(shù)，先對(duì) Title 排序，然后對(duì) Year，最后是時(shí)長：
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
}})一個(gè)長度為 n 的序列進(jìn)行排序需要 O(n logn) 次比較操作，而判斷一個(gè)序列是否已經(jīng)排好序值需要最多 (n-1) 次比較。sort 包提供的 IsSorted 函數(shù)可以判斷序列是否是排好序的。
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))) // 反轉(zhuǎn)
fmt.Println(values) // "[4 3 1 1]"
fmt.Println(sort.IntsAreSorted(values)) // "false"
fmt.Println(sort.IsSorted(sort.Reverse(sort.IntSlice(values)))) // "true"上面的代碼的源碼文件，可以運(yùn)行：
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))) // 反轉(zhuǎn)
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 是不穩(wěn)定的排序。在“優(yōu)化”章節(jié)里的例子，先對(duì)Title進(jìn)行比較，然后是Year，再是Length，實(shí)現(xiàn)了多個(gè)字段的排序。在第一關(guān)鍵字相等的情況下，再通過第二關(guān)鍵字進(jìn)行比較。整個(gè)過程只進(jìn)行了一次序列的交換，這樣看不出問題。
如果對(duì)多個(gè)關(guān)鍵字進(jìn)行排序，但是不是像上面這樣通過一次比較交換完成，而是先對(duì)一個(gè)關(guān)鍵字進(jìn)行排序，得到一個(gè)已經(jīng)有序的序列。然后再在這個(gè)序列的基礎(chǔ)上，再進(jìn)行一次對(duì)另一個(gè)關(guān)鍵字的排序，穩(wěn)定的排序和不穩(wěn)定的排序的結(jié)果就會(huì)有差別。比如排序第一關(guān)鍵字是年齡，第二關(guān)鍵字是姓名。那么先做一個(gè)姓名的排序（穩(wěn)定不穩(wěn)定無所謂），然后再在原來的基礎(chǔ)上做一次年齡的排序（必須穩(wěn)定），才能得到正確的結(jié)果。下面通過具體事例來說明，穩(wěn)定排序和不穩(wěn)定排序的差別。
數(shù)據(jù)結(jié)構(gòu)、打印的函數(shù)、具體數(shù)據(jù)如下代碼實(shí)現(xiàn)：
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] }先對(duì) name 進(jìn)行排序，然后再原來序列的基礎(chǔ)上對(duì) age 進(jìn)行排序：
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)
}最后打印的結(jié)果是這樣的：
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>在這個(gè)結(jié)果里年齡相同的數(shù)據(jù)，并沒有按字母順序排序，雖然之前已經(jīng)按字母順序進(jìn)行了排序，不過在第二次排序的時(shí)候，會(huì)把之前的順序打亂，這就是不穩(wěn)定的排序。
這里來看看穩(wěn)定的排序。這里只要把 sort.Sort 函數(shù)替換成 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)
}這里只替換了第二次排序的函數(shù)。第一次排序的時(shí)候假設(shè)序列本來就是亂的，所以這里并沒有需要穩(wěn)定的必要。
這次再來看下結(jié)果：
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>這次的結(jié)果是期望的樣子了，按年齡排序，如果年齡相同，再按字母順序排序。
sort.Stable 雖然能保證排序的穩(wěn)定性，但是犧牲了效率。如果需要保證序列的穩(wěn)定性，那么就要用 sort.Stable 函數(shù)來代替 sort.Sort。
但是如果僅僅只是要對(duì)多個(gè)字段進(jìn)行排序，也可以直接在比較的時(shí)候就完成全部字段的比較，僅做一次序列的調(diào)換（就是排序）。就向上面“優(yōu)化”章節(jié)里的 customSort 實(shí)現(xiàn)的那樣，下面是這里例子里的實(shí)現(xiàn)：
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)
}創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
