您好,登錄后才能下訂單哦!
排序是一個在很多程序中廣泛使用的操作。sort 包提供了針對任意序列根據任意排序函數原地排序的功能。
這樣的設計號稱并不常見。在很多語言中,排序算法跟序列數據類型綁定,排序函數跟序列元素類型綁定。但 Go 語言的 sort.Sort 函數對序列和其中元素的布局無任何要求,它使用 sort.Interface 接口來實現。
一個原地排序算法需要知道三個信息:
所以 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 這三個類型提供了排序的函數和相關類型。對于其他類型,就需要自己寫了,不過寫起來也不復雜。
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)
}
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。