詳解go語言中sort如何排序

更新時間：2022年03月07日 09:07:58 作者：Zhan-LiZ

我們的代碼業(yè)務(wù)中很多地方需要我們自己進行排序操作，本文主要介紹了詳解go語言中sort如何排序，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

sort 包源碼解讀

前言

我們的代碼業(yè)務(wù)中很多地方需要我們自己進行排序操作，go 標準庫中是提供了 sort 包是實現(xiàn)排序功能的，這里來看下生產(chǎn)級別的排序功能是如何實現(xiàn)的。

go version go1.16.13 darwin/amd64

如何使用

先來看下 sort 提供的主要功能

對基本數(shù)據(jù)類型切片的排序支持
自定義 Less 排序比較器
自定義數(shù)據(jù)結(jié)構(gòu)的排序
判斷基本數(shù)據(jù)類型切片是否已經(jīng)排好序
基本數(shù)據(jù)元素查找

基本數(shù)據(jù)類型切片的排序

sort 包中已經(jīng)實現(xiàn)了對 []int, []float, []string 這幾種類型的排序

func TestSort(t *testing.T) {
?? ?s := []int{5, 2, 6, 3, 1, 4}
?? ?fmt.Println("是否排好序了", sort.IntsAreSorted(s))
?? ?sort.Ints(s)
?? ?// 正序
?? ?fmt.Println(s)
?? ?// 倒序
?? ?sort.Sort(sort.Reverse(sort.IntSlice(s)))
?? ?fmt.Println(s)
?? ?// 穩(wěn)定排序
?? ?sort.Stable(sort.IntSlice(s))
?? ?fmt.Println("是否排好序了", sort.IntsAreSorted(s))
?? ?fmt.Println("查找是否存在", sort.SearchInts(s, 5))
?? ?fmt.Println(s)

?? ?str := []string{"s", "f", "d", "c", "r", "a"}
?? ?sort.Strings(str)
?? ?fmt.Println(str)

?? ?flo := []float64{1.33, 4.78, 0.11, 6.77, 8.99, 4.22}
?? ?sort.Float64s(flo)
?? ?fmt.Println(flo)
}

看下輸出

是否排好序了 false
[1 2 3 4 5 6]
[6 5 4 3 2 1]
是否排好序了 true
查找是否存在 4
[1 2 3 4 5 6]
[a c d f r s]
[0.11 1.33 4.22 4.78 6.77 8.99]

sort 本身不是穩(wěn)定排序，需要穩(wěn)定排序使用sort.Stable，同時排序默認是升序，降序可使用sort.Reverse

自定義 Less 排序比較器

如果我們需要進行的排序的內(nèi)容是一些復雜的結(jié)構(gòu)，例如下面的栗子，是個結(jié)構(gòu)體，根據(jù)結(jié)構(gòu)體中的某一個屬性進行排序，這時候可以通過自定義 Less 比較器實現(xiàn)

使用 sort.Slice，sort.Slice中提供了 less 函數(shù)，我們，可以自定義這個函數(shù)，然后通過sort.Slice進行排序，sort.Slice不是穩(wěn)定排序，穩(wěn)定排序可使用sort.SliceStable

type Person struct {
?? ?Name string
?? ?Age ?int
}

func TestSortSlice(t *testing.T) {
?? ?people := []Person{
?? ??? ?{"Bob", 31},
?? ??? ?{"John", 42},
?? ??? ?{"Michael", 17},
?? ??? ?{"Jenny", 26},
?? ?}

?? ?sort.Slice(people, func(i, j int) bool {
?? ??? ?return people[i].Age < people[j].Age
?? ?})
?? ?// Age正序
?? ?fmt.Println(people)
?? ?// Age倒序
?? ?sort.Slice(people, func(i, j int) bool {
?? ??? ?return people[i].Age > people[j].Age
?? ?})
?? ?fmt.Println(people)

?? ?// 穩(wěn)定排序
?? ?sort.SliceStable(people, func(i, j int) bool {
?? ??? ?return people[i].Age > people[j].Age
?? ?})
?? ?fmt.Println(people)
}

看下輸出

[{Michael 17} {Jenny 26} {Bob 31} {John 42}]
[{John 42} {Bob 31} {Jenny 26} {Michael 17}]
[{John 42} {Bob 31} {Jenny 26} {Michael 17}]

自定義數(shù)據(jù)結(jié)構(gòu)的排序

對自定義結(jié)構(gòu)的排序，除了可以自定義 Less 排序比較器之外，sort 包中也提供了sort.Interface接口，我們只要實現(xiàn)了sort.Interface中提供的三個方法，即可通過 sort 包內(nèi)的函數(shù)完成排序，查找等操作

// An implementation of Interface can be sorted by the routines in this package.
// The methods refer to elements of the underlying collection by integer index.
type Interface interface {
?? ?// Len is the number of elements in the collection.
?? ?Len() int

?? ?// Less reports whether the element with index i
?? ?// must sort before the element with index j.
?? ?//
?? ?// If both Less(i, j) and Less(j, i) are false,
?? ?// then the elements at index i and j are considered equal.
?? ?// Sort may place equal elements in any order in the final result,
?? ?// while Stable preserves the original input order of equal elements.
?? ?//
?? ?// Less must describe a transitive ordering:
?? ?// ?- if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
?? ?// ?- if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
?? ?//
?? ?// Note that floating-point comparison (the < operator on float32 or float64 values)
?? ?// is not a transitive ordering when not-a-number (NaN) values are involved.
?? ?// See Float64Slice.Less for a correct implementation for floating-point values.
?? ?Less(i, j int) bool

?? ?// Swap swaps the elements with indexes i and j.
?? ?Swap(i, j int)
}

來看下如何使用

type ByAge []Person

func (a ByAge) Len() int ? ? ? ? ? { return len(a) }
func (a ByAge) Swap(i, j int) ? ? ?{ a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func TestSortStruct(t *testing.T) {
?? ?people := []Person{
?? ??? ?{"Bob", 31},
?? ??? ?{"John", 42},
?? ??? ?{"Michael", 17},
?? ??? ?{"Jenny", 26},
?? ?}

?? ?sort.Sort(ByAge(people))
?? ?fmt.Println(people)
}

輸出

[{Michael 17} {Jenny 26} {Bob 31} {John 42}]

當然 sort 包中已經(jīng)實現(xiàn)的[]int, []float, []string 這幾種類型的排序也是實現(xiàn)了sort.Interface接口

對于上面的三種排序，第一種和第二種基本上就能滿足我們的額需求了，不過第三種靈活性更強。

分析下源碼

先來看下什么是穩(wěn)定性排序

栗如：對一個數(shù)組進行排序，如果里面有重復的數(shù)據(jù)，排完序時候，相同的數(shù)據(jù)的相對索引位置沒有發(fā)生改變，那么就是穩(wěn)定排序。

也就是里面有兩個5，5。排完之后第一個5還在最前面，沒有和后面的重復數(shù)據(jù)5發(fā)生過位置的互換，那么這就是穩(wěn)定排序。

不穩(wěn)定排序

sort 中的排序算法用到了，quickSort(快排),heapSort(堆排序),insertionSort(插入排序),shellSort(希爾排序)

先來分析下這幾種排序算法的使用

可以看下調(diào)用 Sort 進行排序，最終都會調(diào)用 quickSort

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

再來看下 quickSort 的實現(xiàn)

func quickSort(data Interface, a, b, maxDepth int) {
?? ?// 切片長度大于12的時候使用快排
?? ?for b-a > 12 { // Use ShellSort for slices <= 12 elements
?? ??? ?// maxDepth 返回快速排序應(yīng)該切換的閾值
?? ??? ?// 進行堆排序
?? ??? ?// 當 maxDepth為0的時候進行堆排序
?? ??? ?if maxDepth == 0 {
?? ??? ??? ?heapSort(data, a, b)
?? ??? ??? ?return
?? ??? ?}
?? ??? ?maxDepth--
?? ??? ?// doPivot 是快排核心算法，它取一點為軸，把不大于軸的元素放左邊，大于軸的元素放右邊，返回小于軸部分數(shù)據(jù)的最后一個下標，以及大于軸部分數(shù)據(jù)的第一個下標
?? ??? ?// 下標位置 a...mlo,pivot,mhi...b
?? ??? ?// data[a...mlo] <= data[pivot]
?? ??? ?// data[mhi...b] > data[pivot]
?? ??? ?// 和中位數(shù)一樣的數(shù)據(jù)就不用在進行交換了，維護這個范圍值能減少數(shù)據(jù)的次數(shù) ?
?? ??? ?mlo, mhi := doPivot(data, a, b)
?? ??? ?// 避免遞歸過深
?? ??? ?// 循環(huán)是比遞歸節(jié)省時間的，如果有大規(guī)模的子節(jié)點，讓小的先遞歸，達到了 maxDepth 也就是可以觸發(fā)堆排序的條件了，然后使用堆排序進行排序
?? ??? ?if mlo-a < b-mhi {
?? ??? ??? ?quickSort(data, a, mlo, maxDepth)
?? ??? ??? ?a = mhi // i.e., quickSort(data, mhi, b)
?? ??? ?} else {
?? ??? ??? ?quickSort(data, mhi, b, maxDepth)
?? ??? ??? ?b = mlo // i.e., quickSort(data, a, mlo)
?? ??? ?}
?? ?}
?? ?// 如果切片的長度大于1小于等于12的時候，使用 shell 排序 ?
?? ?if b-a > 1 {
?? ??? ?// Do ShellSort pass with gap 6
?? ??? ?// It could be written in this simplified form cause b-a <= 12
?? ??? ?// 這里先做一輪shell 排序
?? ??? ?for i := a + 6; i < b; i++ {
?? ??? ??? ?if data.Less(i, i-6) {
?? ??? ??? ??? ?data.Swap(i, i-6)
?? ??? ??? ?}
?? ??? ?}
?? ??? ?// 進行插入排序
?? ??? ?insertionSort(data, a, b)
?? ?}
}

// maxDepth 返回快速排序應(yīng)該切換的閾值
// 進行堆排序
func maxDepth(n int) int {
?? ?var depth int
?? ?for i := n; i > 0; i >>= 1 {
?? ??? ?depth++
?? ?}
?? ?return depth * 2
}

// doPivot 是快排核心算法，它取一點為軸，把不大于軸的元素放左邊，大于軸的元素放右邊，返回小于軸部分數(shù)據(jù)的最后一個下標，以及大于軸部分數(shù)據(jù)的第一個下標
// 下標位置 lo...midlo,pivot,midhi...hi
// data[lo...midlo] <= data[pivot]
// data[midhi...hi] > data[pivot]
func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
?? ?m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
?? ?// 這里用到了 Tukey's ninther 算法，文章鏈接 https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/
?? ?// 通過該算法求出中位數(shù)
?? ?if hi-lo > 40 {
?? ??? ?// Tukey's ``Ninther,'' median of three medians of three.
?? ??? ?s := (hi - lo) / 8
?? ??? ?medianOfThree(data, lo, lo+s, lo+2*s)
?? ??? ?medianOfThree(data, m, m-s, m+s)
?? ??? ?medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
?? ?}

?? ?// 求出中位數(shù) data[m] <= data[lo] <= data[hi-1]
?? ?medianOfThree(data, lo, m, hi-1)

?? ?// Invariants are:
?? ?//?? ?data[lo] = pivot (set up by ChoosePivot)
?? ?//?? ?data[lo < i < a] < pivot
?? ?//?? ?data[a <= i < b] <= pivot
?? ?//?? ?data[b <= i < c] unexamined
?? ?//?? ?data[c <= i < hi-1] > pivot
?? ?//?? ?data[hi-1] >= pivot
?? ?// 中位數(shù)
?? ?pivot := lo
?? ?a, c := lo+1, hi-1

?? ?// 處理使 data[lo < i < a] < pivot
?? ?for ; a < c && data.Less(a, pivot); a++ {
?? ?}
?? ?b := a
?? ?for {
?? ??? ?// 處理使 data[a <= i < b] <= pivot
?? ??? ?for ; b < c && !data.Less(pivot, b); b++ {
?? ??? ?}
?? ??? ?// 處理使 data[c <= i < hi-1] > pivot
?? ??? ?for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
?? ??? ?}
?? ??? ?// 左邊和右邊重合或者已經(jīng)在右邊的右側(cè)
?? ??? ?if b >= c {
?? ??? ??? ?break
?? ??? ?}
?? ??? ?// data[b] > pivot; data[c-1] <= pivot
?? ??? ?// 左側(cè)的數(shù)據(jù)大于右側(cè)，交換，然后接著排序
?? ??? ?data.Swap(b, c-1)
?? ??? ?b++
?? ??? ?c--
?? ?}
?? ?// If hi-c<3 then there are duplicates (by property of median of nine).
?? ?// Let's be a bit more conservative, and set border to 5.
?? ?// 如果 hi-c<3 則存在重復項（按中位數(shù)為 9 的屬性）。
?? ?// 讓我們稍微保守一點，將邊框設(shè)置為 5。

?? ?// 因為c為劃分pivot的大小的臨界值，所以在9值劃分時，正常來說，應(yīng)該是兩邊各4個
?? ?// 由于左邊是<=，多了個相等的情況，所以5，3分布，也是沒有問題
?? ?// 如果hi-c<3，c的值明顯偏向于hi，說明有多個和pivot重復值
?? ?// 為了更保守一點，所以設(shè)置為5(反正只是多校驗一次而已)
?? ?protect := hi-c < 5
?? ?// 即便大于等于5，也可能是因為元素總值很多，所以對比hi-c是否小于總數(shù)量的1/4
?? ?if !protect && hi-c < (hi-lo)/4 {
?? ??? ?// 用一些特殊的點和中間數(shù)進行比較
?? ??? ?dups := 0
?? ??? ?// 處理使 data[hi-1] = pivot
?? ??? ?if !data.Less(pivot, hi-1) {
?? ??? ??? ?data.Swap(c, hi-1)
?? ??? ??? ?c++
?? ??? ??? ?dups++
?? ??? ?}
?? ??? ?// 處理使 data[b-1] = pivot
?? ??? ?if !data.Less(b-1, pivot) {
?? ??? ??? ?b--
?? ??? ??? ?dups++
?? ??? ?}
?? ??? ?// m-lo = (hi-lo)/2 > 6
?? ??? ?// b-lo > (hi-lo)*3/4-1 > 8
?? ??? ?// ==> m < b ==> data[m] <= pivot
?? ??? ?if !data.Less(m, pivot) { // data[m] = pivot
?? ??? ??? ?data.Swap(m, b-1)
?? ??? ??? ?b--
?? ??? ??? ?dups++
?? ??? ?}
?? ??? ?// 如果上面的 if 進入了兩次， 就證明現(xiàn)在是偏態(tài)分布（也就是左右不平衡的）
?? ??? ?protect = dups > 1
?? ?}
?? ?// 不平衡，接著進行處理
?? ?// 這里劃分的是<pivot和=pivot的兩組
?? ?if protect {
?? ??? ?// Protect against a lot of duplicates
?? ??? ?// Add invariant:
?? ??? ?//?? ?data[a <= i < b] unexamined
?? ??? ?//?? ?data[b <= i < c] = pivot
?? ??? ?for {
?? ??? ??? ?// 處理使 data[b] == pivot
?? ??? ??? ?for ; a < b && !data.Less(b-1, pivot); b-- {
?? ??? ??? ?}
?? ??? ??? ?// 處理使 data[a] < pivot
?? ??? ??? ?for ; a < b && data.Less(a, pivot); a++ {
?? ??? ??? ?}
?? ??? ??? ?if a >= b {
?? ??? ??? ??? ?break
?? ??? ??? ?}
?? ??? ??? ?// data[a] == pivot; data[b-1] < pivot
?? ??? ??? ?data.Swap(a, b-1)
?? ??? ??? ?a++
?? ??? ??? ?b--
?? ??? ?}
?? ?}
?? ?// 交換中位數(shù)到中間
?? ?data.Swap(pivot, b-1)
?? ?return b - 1, c
}

對于這幾種排序算法的使用，sort 包中是混合使用的

1、如果切片長度大于12的時候使用快排，使用快排的時候，如果滿足了使用堆排序的條件沒這個排序?qū)τ诤竺娴臄?shù)據(jù)的處理，又會轉(zhuǎn)換成堆排序；

2、切片長度小于12了，就使用 shell 排序，shell 排序只處理一輪數(shù)據(jù)，后面數(shù)據(jù)的排序使用插入排序；

堆排序和插入排序就是正常的排序處理了

// insertionSort sorts data[a:b] using insertion sort.
// 插入排序
func insertionSort(data Interface, a, b int) {
?? ?for i := a + 1; i < b; i++ {
?? ??? ?for j := i; j > a && data.Less(j, j-1); j-- {
?? ??? ??? ?data.Swap(j, j-1)
?? ??? ?}
?? ?}
}

// 堆排序
func heapSort(data Interface, a, b int) {
?? ?first := a
?? ?lo := 0
?? ?hi := b - a

?? ?// Build heap with greatest element at top.
?? ?for i := (hi - 1) / 2; i >= 0; i-- {
?? ??? ?siftDown(data, i, hi, first)
?? ?}

?? ?// Pop elements, largest first, into end of data.
?? ?for i := hi - 1; i >= 0; i-- {
?? ??? ?data.Swap(first, first+i)
?? ??? ?siftDown(data, lo, i, first)
?? ?}
}

穩(wěn)定排序

sort 包中也提供了穩(wěn)定的排序，通過調(diào)用sort.Stable來實現(xiàn)

// It makes one call to data.Len to determine n, O(n*log(n)) calls to
// data.Less and O(n*log(n)*log(n)) calls to data.Swap.
func Stable(data Interface) {
?? ?stable(data, data.Len())
}

func stable(data Interface, n int) {
?? ?// 定義切片塊的大小
?? ?blockSize := 20 // must be > 0
?? ?a, b := 0, blockSize
?? ?// 如果切片長度大于塊的大小，分多次對每個塊中進行排序 ? ?
?? ?for b <= n {
?? ??? ?insertionSort(data, a, b)
?? ??? ?a = b
?? ??? ?b += blockSize
?? ?}
?? ?insertionSort(data, a, n)

?? ?// 如果有多個塊，對排好序的塊進行合并操作
?? ?for blockSize < n {
?? ??? ?a, b = 0, 2*blockSize
?? ??? ?for b <= n {
?? ??? ??? ?symMerge(data, a, a+blockSize, b)
?? ??? ??? ?a = b
?? ??? ??? ?b += 2 * blockSize
?? ??? ?}
?? ??? ?if m := a + blockSize; m < n {
?? ??? ??? ?symMerge(data, a, m, n)
?? ??? ?}
?? ??? ?// block 每次循環(huán)擴大兩倍， 直到比元素的總個數(shù)大，就結(jié)束
?? ??? ?blockSize *= 2
?? ?}
}

func symMerge(data Interface, a, m, b int) {
?? ?// 如果只有一個元素避免沒必要的遞歸，這里直接插入
?? ?// 處理左邊部分
?? ?if m-a == 1 {
?? ??? ?// 使用二分查找查找最低索引 i
?? ??? ?// 這樣 data[i] >= data[a] for m <= i < b.
?? ??? ?// 如果不存在這樣的索引，則使用 i == b 退出搜索循環(huán)。
?? ??? ?i := m
?? ??? ?j := b
?? ??? ?for i < j {
?? ??? ??? ?h := int(uint(i+j) >> 1)
?? ??? ??? ?if data.Less(h, a) {
?? ??? ??? ??? ?i = h + 1
?? ??? ??? ?} else {
?? ??? ??? ??? ?j = h
?? ??? ??? ?}
?? ??? ?}
?? ??? ?// Swap values until data[a] reaches the position before i.
?? ??? ?for k := a; k < i-1; k++ {
?? ??? ??? ?data.Swap(k, k+1)
?? ??? ?}
?? ??? ?return
?? ?}

?? ?// 同上
?? ?// 處理右邊部分
?? ?if b-m == 1 {
?? ??? ?// Use binary search to find the lowest index i
?? ??? ?// such that data[i] > data[m] for a <= i < m.
?? ??? ?// Exit the search loop with i == m in case no such index exists.
?? ??? ?i := a
?? ??? ?j := m
?? ??? ?for i < j {
?? ??? ??? ?h := int(uint(i+j) >> 1)
?? ??? ??? ?if !data.Less(m, h) {
?? ??? ??? ??? ?i = h + 1
?? ??? ??? ?} else {
?? ??? ??? ??? ?j = h
?? ??? ??? ?}
?? ??? ?}
?? ??? ?// Swap values until data[m] reaches the position i.
?? ??? ?for k := m; k > i; k-- {
?? ??? ??? ?data.Swap(k, k-1)
?? ??? ?}
?? ??? ?return
?? ?}

?? ?for start < r {
?? ??? ?c := int(uint(start+r) >> 1)
?? ??? ?if !data.Less(p-c, c) {
?? ??? ??? ?start = c + 1
?? ??? ?} else {
?? ??? ??? ?r = c
?? ??? ?}
?? ?}

?? ?end := n - start
?? ?if start < m && m < end {
?? ??? ?rotate(data, start, m, end)
?? ?}
?? ?// 遞歸的進行歸并操作
?? ?if a < start && start < mid {
?? ??? ?symMerge(data, a, start, mid)
?? ?}
?? ?if mid < end && end < b {
?? ??? ?symMerge(data, mid, end, b)
?? ?}
}

對于穩(wěn)定排序，用到了插入排序和歸并排序

1、首先會將數(shù)據(jù)按照每20個一組進行分塊，對每個塊中的數(shù)據(jù)使用插入排序完成排序；

2、然后下面使用歸并排序，對排序的數(shù)據(jù)塊進行兩兩歸并排序，完成一次排序，擴大數(shù)據(jù)塊為之前的2倍，直到完成所有的排序。

查找

sort 中的查找功能最終是調(diào)用 search 函數(shù)來實現(xiàn)的

func SearchInts(a []int, x int) int {
?? ?return Search(len(a), func(i int) bool { return a[i] >= x })
}

// 使用二分查找
func Search(n int, f func(int) bool) int {
?? ?// Define f(-1) == false and f(n) == true.
?? ?// Invariant: f(i-1) == false, f(j) == true.
?? ?i, j := 0, n
?? ?for i < j {
? ? ? ? ? ? ? ? // 二分查找
?? ??? ?h := int(uint(i+j) >> 1) // avoid overflow when computing h
?? ??? ?// i ≤ h < j
?? ??? ?if !f(h) {
?? ??? ??? ?i = h + 1 // preserves f(i-1) == false
?? ??? ?} else {
?? ??? ??? ?j = h // preserves f(j) == true
?? ??? ?}
?? ?}
?? ?// i == j, f(i-1) == false, and f(j) (= f(i)) == true ?=> ?answer is i.
?? ?return i
}

sort 中查找相對比較簡單，使用的是二分查找

Interface

sort 包提供了 Interface 的接口，我們可以自定義數(shù)據(jù)結(jié)構(gòu)，然后實現(xiàn) Interface 對應(yīng)的接口，就能使用 sort 包中的方法

type Interface interface {
?? ?Len() int

?? ?Less(i, j int) bool

?? ?Swap(i, j int)
}

看源碼可以看到 sort 包中已有的對 []int 等數(shù)據(jù)結(jié)構(gòu)的排序，也是實現(xiàn)了 Interface

// Convenience types for common cases

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int

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

這種思路挺好的，之后可以借鑒下，對于可變部分提供抽象接口，讓用戶根據(jù)自己的場景有實現(xiàn)。

對于基礎(chǔ)的排序，查找只要實現(xiàn)了 Interface 的方法，就能擁有這些基礎(chǔ)的能力了。