C語言中文網 目錄
首頁 > Go語言教程 > Go語言接口 閱讀:2,953

Go語言排序(借助sort.Interface接口)

排序是常見的算法之一,也是常見的面試題之一,程序員對各種排序算法也是津津樂道。實際使用中,語言的類庫會為我們提供健壯、高性能的排序算法庫,開發者在了解排序算法基本原理的基礎上,應該避免“造輪子”,直接使用已有的排序算法庫,以縮短開發周期,提高開發效率。

Go語言中在排序時,需要使用者通過 sort.Interface 接口提供數據的一些特性和操作方法。接口定義代碼如下:
type Interface interface {
    // 獲取元素數量
    Len() int
    
    // 小于比較
    Less(i, j int) bool
    
    // 交換元素
    Swap(i, j int)
}
代碼說明如下:
  • 第 3 行,排序算法需要實現者提供需要排序的數據元素數量。
  • 第 6 行,排序需要通過比較元素之間的關系才能做出具體的操作。Less() 方法需要提供兩個給定索引(i 和 j)對應元素的小于比較(數值的 < 操作)的結果。參數的 i、j 傳入的是元素的索引。將傳入的 i、j 索引對應的元素按小于關系進行比較,完成后把結果通過 Less() 方法的返回值返回。
  • 第 9 行,排序的過程就是不停地交換元素。Swap() 方法需要實現者通過傳入 i、j 索引找到元素,并交換元素的值。

這個接口需要實現者實現的方法就是排序的經典操作:數量(Len)、比較(Less)、交換(Swap)。

使用sort.Interface接口進行排序

對一系列字符串進行排序時,使用字符串切片([]string)承載多個字符串。使用 type 關鍵字,將字符串切片([]string)定義為自定義類型 MyStringList。為了讓 sort 包能識別 MyStringList,能夠對 MyStringList 進行排序,就必須讓 MyStringList 實現 sort.Interface 接口。

下面是對字符串排序的詳細代碼(代碼1):
package main

import (
    "fmt"
    "sort"
)

// 將[]string定義為MyStringList類型
type MyStringList []string

// 實現sort.Interface接口的獲取元素數量方法
func (m MyStringList) Len() int {
    return len(m)
}

// 實現sort.Interface接口的比較元素方法
func (m MyStringList) Less(i, j int) bool {
    return m[i] < m[j]
}

// 實現sort.Interface接口的交換元素方法
func (m MyStringList) Swap(i, j int) {
    m[i], m[j] = m[j], m[i]
}

func main() {

    // 準備一個內容被打亂順序的字符串切片
    names := MyStringList{
        "3. Triple Kill",
        "5. Penta Kill",
        "2. Double Kill",
        "4. Quadra Kill",
        "1. First Blood",
    }

    // 使用sort包進行排序
    sort.Sort(names)

    // 遍歷打印結果
    for _, v := range names {
            fmt.Printf("%s\n", v)
    }

}
代碼輸出結果:
1. First Blood
2. Double Kill
3. Triple Kill
4. Quadra Kill
5. Penta Kill

代碼說明如下:
  • 第 9 行,接口實現不受限于結構體,任何類型都可以實現接口。要排序的字符串切片 []string 是系統定制好的類型,無法讓這個類型去實現 sort.Interface 排序接口。因此,需要將 []string 定義為自定義的類型。
  • 第 12 行,實現獲取元素數量的 Len() 方法,返回字符串切片的元素數量。
  • 第 17 行,實現比較元素的 Less() 方法,直接取 m 切片的 i 和 j 元素值進行小于比較,并返回比較結果。
  • 第 22 行,實現交換元素的 Swap() 方法,這里使用 Go 語言的多變量賦值特性實現元素交換。
  • 第 29 行,由于將 []string 定義成 MyStringList 類型,字符串切片初始化的過程等效于下面的寫法:
    names := []string {
        "3. Triple Kill",
        "5. Penta Kill",
        "2. Double Kill",
        "4. Quadra Kill",
        "1. First Blood",
    }
  • 第 38 行,使用 sort 包的 Sort() 函數,將 names(MyStringList類型)進行排序。排序時,sort 包會通過 MyStringList 實現的 Len()、Less()、Swap() 這 3 個方法進行數據獲取和修改。
  • 第 41 行,遍歷排序好的字符串切片,并打印結果。

常見類型的便捷排序

通過實現 sort.Interface 接口的排序過程具有很強的可定制性,可以根據被排序對象比較復雜的特性進行定制。例如,需要多種排序邏輯的需求就適合使用 sort.Interface 接口進行排序。但大部分情況中,只需要對字符串、整型等進行快速排序。Go 語言中提供了一些固定模式的封裝以方便開發者迅速對內容進行排序。

1) 字符串切片的便捷排序

sort 包中有一個 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] }

// Sort is a convenience method.
func (p StringSlice) Sort() { Sort(p) }
sort 包中的 StringSlice 的代碼與 MyStringList 的實現代碼幾乎一樣。因此,只需要使用 sort 包的 StringSlice 就可以更簡單快速地進行字符串排序。將代碼1中的排序代碼簡化后如下所示:
names := sort.StringSlice{
    "3. Triple Kill",
    "5. Penta Kill",
    "2. Double Kill",
    "4. Quadra Kill",
    "1. First Blood",
}

sort.Sort(names)
簡化后,只要兩句代碼就實現了字符串排序的功能。

2) 對整型切片進行排序

除了字符串可以使用 sort 包進行便捷排序外,還可以使用 sort.IntSlice 進行整型切片的排序。sort.IntSlice 的定義如下:
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] }

// Sort is a convenience method.
func (p IntSlice) Sort() { Sort(p) }
sort 包在 sort.Interface 對各類型的封裝上還有更進一步的簡化,下面使用 sort.Strings 繼續對代碼1進行簡化,代碼如下:
names := []string{
    "3. Triple Kill",
    "5. Penta Kill",
    "2. Double Kill",
    "4. Quadra Kill",
    "1. First Blood",
}

sort.Strings(names)

// 遍歷打印結果
for _, v := range names {
    fmt.Printf("%s\n", v)
}
代碼說明如下:
  • 第 1 行,需要排序的字符串切片。
  • 第 9 行,使用 sort.Strings 直接對字符串切片進行排序。

3) sort包內建的類型排序接口一覽

Go 語言中的 sort 包中定義了一些常見類型的排序方法,如下表所示。

sort 包中內建的類型排序接口
類  型 實現 sort.lnterface 的類型 直接排序方法 說  明
字符串(String) StringSlice sort.Strings(a [] string) 字符 ASCII 值升序
整型(int) IntSlice sort.Ints(a []int) 數值升序
雙精度浮點(float64) Float64Slice sort.Float64s(a []float64) 數值升序

編程中經常用到的 int32、int64、float32、bool 類型并沒有由 sort 包實現,使用時依然需要開發者自己編寫。

對結構體數據進行排序

除了基本類型的排序,也可以對結構體進行排序。結構體比基本類型更為復雜,排序時不能像數值和字符串一樣擁有一些固定的單一原則。結構體的多個字段在排序中可能會存在多種排序的規則,例如,結構體中的名字按字母升序排列,數值按從小到大的順序排序。一般在多種規則同時存在時,需要確定規則的優先度,如先按名字排序,再按年齡排序等。

1) 完整實現sort.Interface進行結構體排序

將一批英雄名單使用結構體定義,英雄名單的結構體中定義了英雄的名字和分類。排序時要求按照英雄的分類進行排序,相同分類的情況下按名字進行排序,詳細代碼實現過程如下。

結構體排序代碼(代碼2):
package main

import (
    "fmt"
    "sort"
)

// 聲明英雄的分類
type HeroKind int

// 定義HeroKind常量, 類似于枚舉
const (
    None HeroKind = iota
    Tank
    Assassin
    Mage
)

// 定義英雄名單的結構
type Hero struct {
    Name string  // 英雄的名字
    Kind HeroKind  // 英雄的種類
}

// 將英雄指針的切片定義為Heros類型
type Heros []*Hero

// 實現sort.Interface接口取元素數量方法
func (s Heros) Len() int {
    return len(s)
}

// 實現sort.Interface接口比較元素方法
func (s Heros) Less(i, j int) bool {

    // 如果英雄的分類不一致時, 優先對分類進行排序
    if s[i].Kind != s[j].Kind {
        return s[i].Kind < s[j].Kind
    }

    // 默認按英雄名字字符升序排列
    return s[i].Name < s[j].Name
}

// 實現sort.Interface接口交換元素方法
func (s Heros) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {

    // 準備英雄列表
    heros := Heros{
        &Hero{"呂布", Tank},
        &Hero{"李白", Assassin},
        &Hero{"妲己", Mage},
        &Hero{"貂蟬", Assassin},
        &Hero{"關羽", Tank},
        &Hero{"諸葛亮", Mage},
    }

    // 使用sort包進行排序
    sort.Sort(heros)

    // 遍歷英雄列表打印排序結果
    for _, v := range heros {
        fmt.Printf("%+v\n", v)
    }
}
代碼輸出如下:
&{Name:關羽 Kind:1}
&{Name:呂布 Kind:1}
&{Name:李白 Kind:2}
&{Name:貂蟬 Kind:2}
&{Name:妲己 Kind:3}
&{Name:諸葛亮 Kind:3}

代碼說明如下:
  • 第 9 行,將 int 聲明為 HeroKind 英雄類型,后面會將這個類型當做枚舉來使用。
  • 第 13 行,定義一些英雄類型常量,可以理解為枚舉的值。
  • 第 26 行,為了方便實現 sort.Interface 接口,將 []*Hero 定義為 Heros 類型。
  • 第 29 行,Heros 類型實現了 sort.Interface 的 Len() 方法,返回英雄的數量。
  • 第 34 行,Heros 類型實現了 sort.Interface 的 Less() 方法,根據英雄字段的比較結果決定如何排序。
  • 第 37 行,當英雄的分類不一致時,優先按分類的枚舉數值從小到大排序。
  • 第 42 行,英雄分類相等的情況下,默認根據英雄的名字字符升序排序。
  • 第 46 行,Heros 類型實現了 sort.Interface 的 Swap() 方法,交換英雄元素的位置。
  • 第 53~60 行,準備一系列英雄數據。
  • 第 63 行,使用 sort 包進行排序。
  • 第 66 行,遍歷所有排序完成的英雄數據。

2) 使用sort.Slice進行切片元素排序

從 Go 1.8 開始,Go 語言在 sort 包中提供了 sort.Slice() 函數進行更為簡便的排序方法。sort.Slice() 函數只要求傳入需要排序的數據,以及一個排序時對元素的回調函數,類型為 func(i,j int)bool,sort.Slice() 函數的定義如下:
func Slice(slice interface{}, less func(i, j int) bool)
使用 sort.Slice() 函數,對代碼2重新優化的完整代碼如下:
package main

import (
    "fmt"
    "sort"
)

type HeroKind int

const (
    None = iota
    Tank
    Assassin
    Mage
)

type Hero struct {
    Name string
    Kind HeroKind
}

func main() {

    heros := []*Hero{
        {"呂布", Tank},
        {"李白", Assassin},
        {"妲己", Mage},
        {"貂蟬", Assassin},
        {"關羽", Tank},
        {"諸葛亮", Mage},
    }

    sort.Slice(heros, func(i, j int) bool {
        if heros[i].Kind != heros[j].Kind {
            return heros[i].Kind < heros[j].Kind
        }

        return heros[i].Name < heros[j].Name
    })

    for _, v := range heros {
        fmt.Printf("%+v\n", v)
    }
}
第 33 行到第 39 行加粗部分是新添加的 sort.Slice() 及回調函數部分。對比前面的代碼,這里去掉了 Heros 及接口實現部分的代碼。

使用 sort.Slice() 不僅可以完成結構體切片排序,還可以對各種切片類型進行自定義排序。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo