切片是Go語言中引入的用于在大多數場合替代數組的文法元素。切片是一種長度可變的同類型元素序列，它原則上不支援存儲不同類型的元素，當然了作為打勞工是非常清楚“原則上”的潛台詞就是“某種情況下允許”

special := []interface{}{“hello go”, 2021, 4.15}

複制

這種允許的情況有機會我們另外讨論，這個不是本次的讨論範圍，本文就事論事，還不至于深入到原理。

正所謂有序列的地方就有排序的需求。在各種排序算法都已經成熟的今天，我們完全可以針對特定元素類型的切片手寫排序函數/方法，但多數情況下不推薦這麼做，因為Go标準庫内置了

sort

包可以很好地幫助我們實作原生類型元素切片以及自定義類型元素切片的排序任務，但話又說回來，工程項目中我們大機率都是拿來主義的，也隻有是在平常刷題練習中才會自己考慮實作相關的算法。

對于sort

Go 的排序思路和 C 和 C++ 有些差别。 C 預設是對數組進行排序， C++ 是對一個序列進行排序， Go 則更寬泛一些，待排序的可以是任何對象，雖然很多情況下是一個

slice

(分片, 類似于數組)，或是包含 slice 的一個對象。

這個包實作了四種基本排序算法：插入排序、歸并排序、堆排序和快速排序。但是這四種排序方法是不公開的，它們隻被用于

sort

包内部使用。是以在對資料集合排序時不必考慮應當選擇哪一種排序方法，隻要實作了

sort.Interface

定義的三個方法：

擷取資料集合長度的 Len() 方法
比較兩個元素大小的 Less() 方法
交換兩個元素位置的 Swap() 方法

完成之後可以順利對資料集合進行排序【無時不刻在等待泛型的出現啊，重複寫真的煩:)】

sort 包會根據實際資料自動選擇高效的排序算法。除此之外，為了友善對常用資料類型的操作，sort 包提供了對

[]int

切片、

[]float64

切片和

[]string

切片完整支援，主要包括：

對基本資料類型切片的排序支援
基本資料元素查找
判斷基本資料類型切片是否已經排好序
對排好序的資料集合逆序

資料集合排序

前面已經提到過，對資料集合（包括自定義資料類型的集合）排序需要實作 sort.Interface 接口的三個方法，我們看以下該接口的定義：

type Interface interface {
    // 擷取資料集合元素個數
    Len() int
    // 如果 i 索引的資料小于 j 索引的資料，傳回 true，且不會調用下面的 Swap()，即資料升序排序。
    Less(i, j int) bool
    // 交換 i 和 j 索引的兩個元素的位置
    Swap(i, j int)
}

複制

資料集合實作了這三個方法後，即可調用該包的

Sort()

方法進行排序。

Sort()

方法定義如下：

func Sort(data Interface)

複制

Sort() 方法使用的惟一參數就是待排序的資料集合。

此外該包還提供了一個方法可以判斷資料集合是否已經排好順序，畢竟方法的内部實作依賴于我們自己實作的 Len() 和 Less() 方法：

func IsSorted(data Interface) bool {
    n := data.Len()
    for i := n - 1; i > 0; i-- {
        if data.Less(i, i-1) {
            return false
        }
    }
    return true
}

複制

最後一個方法：

Search()

func Search(n int, f func(int) bool) int

複制

該方法會使用“二分查找”算法來找出能使

f(x)(0<=x<n)

傳回 ture 的最小值 i。前提條件 :

f(x)(0<=x<i)

均傳回

false

f(x)(i<=x<n)

均傳回

ture

。如果不存在 i 可以使 f(i) 傳回 ture, 則傳回 n。

Search() 函數一個常用的使用方式是搜尋元素 x 是否在已經升序排好的切片 s 中：

x := 11
s := []int{3, 6, 8, 11, 45} // 注意已經升序排序
pos := sort.Search(len(s), func(i int) bool { return s[i] >= x })
if pos < len(s) && s[pos] == x {
    fmt.Println(x, " 在 s 中的位置為：", pos)
} else {
    fmt.Println("s 不包含元素 ", x)
}

複制

排序原理

截至目前Go 1.15版本，Go還不支援泛型。是以，為了支援任意元素類型的切片的排序，标準庫sort包定義了一個

Interface

接口和一個接受該接口類型參數的

Sort

函數：

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

func Sort(data Interface) {
        n := data.Len()
        quickSort(data, 0, n, maxDepth(n))
}

複制

為了應用這個排序函數Sort，我們需要讓被排序的切片類型實作

sort.Interface

接口，以整型切片為例

type IntSlice []int

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

func main() {
    sl := IntSlice([]int{89, 14, 8, 9, 17, 56, 95, 3})
    fmt.Println(sl) // [89 14 8 9 17 56 95 3]
    sort.Sort(sl)
    fmt.Println(sl) // [3 8 9 14 17 56 89 95]
}

複制

從

sort.Sort

函數的實作來看，它使用的是快速排序

quickSort

。我們知道快速排序是在所有數量級為

O(nlogn)

的排序算法中其平均性能最好的算法，但在某些情況下其性能卻并非最佳，Go sort包中的

quickSort

函數也沒有嚴格拘泥于僅使用快排算法，而是以快速排序為主，并根據目标狀況在特殊條件下選擇了其他不同的排序算法，包括堆排序(heapSort)、插入排序(insertionSort)等。

sort.Sort函數不保證排序是穩定的，要想使用穩定排序，需要使用

sort.Stable

函數。

sort包的“文法糖”排序函數

我們看到，直接使用sort.Sort函數對切片進行排序是比較繁瑣的。如果僅僅排序一個原生的整型切片都這麼繁瑣(要實作三個方法），那麼sort包是會被噴慘的。還好，對于以常見原生類型為元素的切片，sort包提供了類“文法糖”的簡化函數，比如：

sort.Ints

、

sort.Float64s

和

sort.Strings

等。上述整型切片的排序代碼可以直接改造成下面這個樣子：

func main() {
    sl := []int{89, 14, 8, 9, 17, 56, 95, 3}
    fmt.Println(sl) // [89 14 8 9 17 56 95 3]
    sort.Ints(sl)
    fmt.Println(sl) // [3 8 9 14 17 56 89 95]
}

複制

原生類型有“文法糖”可用了，那麼對于自定義類型作為元素的切片，是不是每次都得實作Interface接口的三個方法呢？Go團隊也想到了這個問題! 是以在Go 1.8版本中加入了

sort.Slice

函數，我們隻需傳入一個比較函數實作即可：

type Lang struct {
    Name string
    Rank int
}

func main() {
    langs := []Lang{
        {"rust", 2},
        {"go", 1},
        {"swift", 3},
    }
    sort.Slice(langs, func(i, j int) bool { return langs[i].Rank < langs[j].Rank })
    fmt.Printf("%v\n", langs) // [{go 1} {rust 2} {swift 3}]
}

複制

同理，如果要進行穩定排序，則用

sort.SliceStable

替換上面的

sort.Slice

。

總結

本文主要是通過對go中切片的分析，由于go中的排序不同于c、c++、python這些語言的排序習慣，又由于其不支援泛型，且正處于野蠻生長期，我們在學習應用的過程中，也難得的可以體驗其發育帶來痛苦，正因為沒有體會相同的痛苦，就不能感同身受，成熟的語言如java、python用多了，一直用别人的輪子，實在體會不到輪子内部的精妙之處，我們在學習的過程中可以自己實作相關的排序算法，見證社群的發展，反而可以一步步推演核心的進化，進而觸類旁通猜測其他語言的設計思想，不勝榮幸。

參考資料

https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.1.html
https://golang.org/pkg/sort/
https://tonybai.com/2020/11/26/slice-sort-in-go/
https://itimetraveler.github.io/2016/09/07/%E3%80%90Go%E8%AF%AD%E8%A8%80%E3%80%91%E5%9F%BA%E6%9C%AC%E7%B1%BB%E5%9E%8B%E6%8E%92%E5%BA%8F%E5%92%8C%20slice%20%E6%8E%92%E5%BA%8F/

淺析go切片與排序對于sort總結參考資料

對于sort

資料集合排序

排序原理

sort包的“文法糖”排序函數

總結

參考資料