Go中的三種排序方法
- 2019 年 12 月 30 日
- 筆記
排序是很多程式經常使用的操作。儘管一個簡短的快排程式只要二三十行程式碼就可以搞定，但是一個健壯的實現需要更多的程式碼，並且我們不希望每次我們需要的時候都重寫或者拷貝這些程式碼。幸運的是，Go內置的 sort包中提供了根據一些排序函數來對任何序列進行排序的功能。
排序整數、浮點數和字元串切片
對於 []int, []float, []string這種元素類型是基礎類型的切片使用sort包提供的下面幾個函數進行排序。
- sort.Ints
- sort.Floats
- sort.Strings
s := []int{4, 2, 3, 1} sort.Ints(s) fmt.Println(s) // 輸出[1 2 3 4]
使用自定義比較器排序
- 使用
sort.Slice函數排序，它使用一個用戶提供的函數來對序列進行排序，函數類型為func(i,jint)bool，其中參數i,j是序列中的索引。 sort.SliceStable在排序切片時會保留相等元素的原始順序。- 上面兩個函數讓我們可以排序結構體切片(order by struct field value)。
family := []struct { Name string Age int }{ {"Alice", 23}, {"David", 2}, {"Eve", 2}, {"Bob", 25}, } // 用 age 排序，年齡相等的元素保持原始順序 sort.SliceStable(family, func(i, j int) bool { return family[i].Age < family[j].Age }) fmt.Println(family) // [{David 2} {Eve 2} {Alice 23} {Bob 25}]
排序任意數據結構
- 使用
sort.Sort或者sort.Stable函數。 - 他們可以排序實現了sort.Interface介面的任意類型
一個內置的排序演算法需要知道三個東西：序列的長度，表示兩個元素比較的結果，一種交換兩個元素的方式；這就是sort.Interface的三個方法：
type Interface interface { Len() int Less(i, j int) bool // i, j 是元素的索引 Swap(i, j int) }
還是以上面的結構體切片為例子，我們為切片類型自定義一個類型名，然後在自定義的類型上實現 srot.Interface 介面
type Person struct { Name string Age int } // ByAge 通過對age排序實現了sort.Interface介面 type ByAge []Person 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() { family := []Person{ {"David", 2}, {"Alice", 23}, {"Eve", 2}, {"Bob", 25}, } sort.Sort(ByAge(family)) fmt.Println(family) // [{David, 2} {Eve 2} {Alice 23} {Bob 25}] }
實現了sort.Interface的具體類型不一定是切片類型；下面的customSort是一個結構體類型。
type customSort struct { p []*Person less func(x, y *Person) bool } func (x customSort) Len() int {len(x.p)} 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.p[i], x.p[j] = x.p[j], x.p[i] }
讓我們定義一個根據多欄位排序的函數，它主要的排序鍵是Age，Age 相同了再按 Name 進行倒序排序。下面是該排序的調用，其中這個排序使用了匿名排序函數：
sort.Sort(customSort{persons, func(x, y *Person) bool { if x.Age != y.Age { return x.Age < y.Age } if x.Name != y.Name { return x.Name > y.Name } return false }})
排序具體的演算法和複雜度
Go 的 sort包中所有的排序演算法在最壞的情況下會做 n * log n次 比較，n 是被排序序列的長度，所以排序的時間複雜度是 O(n log n)。其大多數的函數都是用改良後的快速排序演算法實現的。
