從 JavaScript 到 Go 語言的排序算法

在計算機科學中，排序的意思是獲取一個數組，然後重新對他們進行排列，使他們遵循指定的順序，例如按字母順序對字符串進行排序、按最小到最大的順序對數字進行排序，或按結構中的一個字段對結構數組進行排序。您可以使用它（排序）來提高算法的工作效率，或按特定順序顯示數據（例如時間上的從最近到最遠）。

對於 Go 中的排序，標準庫提供了 sort 包，有意思的是，它使用了 Go 接口來定義對數據進行排序的規則。如果您使用過 JavaScript 的 Array.prototype.sort 方法，（那麼，您對此）會很熟悉！

字符串排序

讓我們從按字母順序排列一組字符串開始：

var languages = []string{"Go", "C", "Ruby", "JavaScript", "XML"}

在 JavaScript 中，對它們進行排序（代碼）就像這樣：

let languages = ["Go", "C", "Ruby", "JavaScript", "XML"];

languages.sort();
console.log(languages); // ["C", "Go", "JavaScript", "Ruby", "XML"]

由於 languages 是一個數組，我們可以使用 Array.prototype.sort, 對它們進行排序。

由於與 JS 數組不同，Go 切片沒有開箱即用的方法，我們沒辦法直接使用已有的排序算法，我們需要導入 sort 包並使用其 Sort 函數來對數組重新排列。讓我們試試吧！（首先，）將此代碼放在一個名爲 sort-strings.go 的文件中：

package main

import (
 "fmt"
 "sort"
)

func main() {
 languages := []string{"Go", "C", "Ruby", "JavaScript", "XML"}
 sort.Sort(languages)

 fmt.Println(languages)
}

然後，運行 go run sort-strings.go，你應該會得到（如下錯誤）：

./sort-strings.go:10:14: cannot use languages (type []string) as type sort.Interface in argument to sort.Sort:
 []string does not implement sort.Interface (missing Len method)

編譯器錯誤？之所以會這樣，是因爲 sort.Sort 不接受切片類型，它無法對切片類型進行自動轉換。它的函數簽名實際上是這樣的：

func Sort(data Interface)

sort.Interface（帶有一個大 I）是一個 Go 接口，表示可以排序的數據集合，如字符串、數字抑或是結構體列表。由於對字符串和整數的切片進行排序很常見，所以 sort 包也提供了一些內置方法，使 sort.Sort 方法與字符串或整數切片可以兼容. 試試這個！

func main() {
 languages := []string{"Go", "C", "Ruby", "JavaScript", "XML"}
- sort.Sort(languages)
+ sort.Sort(sort.StringSlice(languages))

 fmt.Println(languages)
}

sort.StringSlice 是一個字符串切片方法，但它實現了 sort.Interface 接口. 因此，通過將一個 []string 類型轉換爲 StringSlice 類型，就可以使用 sort.Sort! 現在，如果您（再）執行 go run sort-strings.go 命令，您應該會看到按字母順序排列的編程語言列表！

爲什麼我們需要使用一個特殊的接口來對數據進行排序，而不是讓 Go 語言的 sort.Sort 方法直接接受（字符串或整型）切片？原因是因爲，我們傳入的是一個元素集合，Go 語言需要通過某種方法來知道元素的順序。爲了編寫這些規則來對切片進行排序，您需要實現 sort.Interface 方法。正如您看到的，Interface 使我們可以靈活地以任何您喜歡的方式來定義元素的順序！

實現自定義排序類型

假設我們的 languages 切片包含 "fish"（一種 shell 腳本語言）。如果您按字母順序對 "編程工具" 進行排序，那麼像這樣有意義的排序是：

[C, fish, Go, JavaScript, Ruby, XML]

但是，即使有 XML，"fish" 也排在最後！（這是因爲）使用 sort.StringSlice, 與使用 JS 中的字符串列表排序算法 Array.prototype.sort 相同，默認按照字典順序排序，而不是字母順序。在字典順序中，小寫字母（如 fish 中的 f）在大寫字母（如 XML 中的 X）之後。如果我們想不區分大小寫，就按照字母的順序排序，我們需要實現一些自定義行爲。那會是什麼樣子呢？

在實現自定義排序規則之前，我們需要想想排序的作用。在本教程中，我們不會研究不同排序算法（如快速排序、歸併排序和冒泡排序）的細節，雖然學習它們在編程中很重要。關於在 Go 和 JS 中編寫自定義排序算法，您需要了解的是，它們需具備：

在 JavaScript 中，您將傳入一個自定義函數來告訴 sort 如何對數組中的元素進行比較，如下所示：

languages.sort((langA, langB) => {
 langA = langA.toLowerCase();
 langB = langB.toLowerCase();
 if (langA < langB) {
  return -1; // return -1 if langA should Go before langB in the array
 } else if (langB > langA) {
  return 1;  // return 1 if langB should Go before langA in the array
 }
 return 0;    // return 0 if they can Go in either order
})

因爲我們在比較之前已使用 toLowerCase 方法，（這樣可以）使得 fish 語言排在 Go、JavaScript、Ruby 和 XML 語言之前，但在 C 語言之後！

如果我們查看 Go sort.Interface，我們可以看到需要實現的方法如下：

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

所以要創建一個可以排序的類型，我們需要實現 sort.Interface 接口：

讓我們以 Len 和 Swap 的實現方法開始。

type alphabeticalStrings []string

func (a alphabeticalStrings) Len() int { return len(a) }

func (a alphabeticalStrings) Swap(i, j int) {
 placeholder := a[j]
 a[j] = a[i]
 a[i] = placeholder
}

首先，我們對字符串切片進行封裝，定義一個新的類型，alphabeticalStrings。在 Go 語言中，我們通過定義自己的類型，我們可以爲它編寫方法。

對於 Len 方法，我們只是使用 Go 的內置 len 函數來獲取切片的長度，對於 Swap，我們交換切片中的兩個元素。目前爲止一切順利。現在讓我們實現 Less 方法。先導入 strings 包，並添加這個函數：

func (a alphabeticalStrings) Less(i, j int) bool {
 return strings.ToLower(a[i]) < strings.ToLower(a[j])
}

注意到關於 Less 方法了嗎？它看起來非常像我們在 Array.prototype.sort 函數中定義的比較方法，除了它返回一個 bool 類型而不是 int 類型，並接受的是切片索引而不是元素本身！

現在，讓我們來試試！編輯 main 函數，讓它像這樣：

func main() {
 languages := []string{"Go", "C", "fish", "Ruby", "JavaScript", "XML"}
- sort.Sort(sort.StringSlice(languages))
+ sort.Sort(alphabeticalStrings(languages))

 fmt.Println(languages)
}

如果您執行 go run sort-strings.go 命令，現在您應該可以看到按預期排序的列表！

[C, fish, Go, JavaScript, Ruby, XML]

你知道 Go 有什麼好玩的 sort.Interface 接口嗎？我們編寫的字母字符串類型和 Go 團隊編寫的 StringSlice 類型都建立在一個普通的舊類型之上，[]string 並且都可以傳遞到 sort.Sort. 我們可以通過選擇我們將字符串切片轉換爲哪種類型來選擇我們想要的字符串順序！

使用 sort.Slice 簡化我們的排序！

JS 和 Go 語言不同版本的 sort 方法之間的一個重要區別是，對 Go 切片進行排序時，除了比較函數之外，我們還需要編寫 Len 和 Swap 方法。對於不同的切片類型，Len 和 Swap 看起來都差不多。故，定義一個新的（元素）排序，都必須實現這三種方法感覺有點麻煩。

需要實現這三種方法的原因是，你實現 sort.Interface 接口時，對應的數據，並不一定是數組或切片。我只是使用了切片的 sort 包，但您可以使用其他數據類型實現 sort.Interface 接口，例如鏈表。

對於切片，在 Len 和 Swap 方法中，我們經常使用的是相同的邏輯，我們能不能只實現 Less，就像在 JavaScript 中一樣？（其實）sort 包就有這樣的方法，sort.Slice！

func Slice(
 slice interface{},
 less func(i, j int) bool,
)

我們傳入我們想要排序的數據切片作爲第一個參數，以及一個函數來比較切片的元素作爲第二個參數。甚至無需創建新類型，現在我們就可以對數據進行排序！讓我們再一次重構我們的 main 函數來試試：

func main() {
 languages := []string{"Go", "C", "fish", "Ruby", "JavaScript", "XML"}
- sort.Sort(alphabeticalStrings(languages))
+ sort.Slice(languages, func(i, j int) bool {
+   return strings.ToLower(languages[i]) < strings.ToLower(languages[j])
+ })

 fmt.Println(languages)
}

完成了！我們已經獲取到我們要的排序切片了！

sort 包還有一些很酷的地方，除了我們能夠選擇排序所依據的順序外，注意在 sort.Sort 和 sort.Slice 中，我們不需要知道我們正在使用哪種排序算法。sort.Sort 已包含了具體的實現算法，所有需要從我們這邊獲取到的信息是，如何比較元素，如何交換它們，以及我們有多少元素。這就是接口的作用！

順便說一下，熟悉排序算法的工作原理仍然是絕對值得的，這會讓您知道如何讓你的計算機做更少的工作來排列數據，而其（原理）的應用場景非常多。因此，如果您想了解它們是如何工作，sort.Sort 和我們編寫的這些函數在背後都做了什麼，下面是一些關於算法本身的材料（可供學習）。

via: https://dev.to/andyhaskell/sorting-in-go-from-javascript-4k8o

作者：andyhaskell[4] 譯者：gogeof[5] 校對：polaris1119[6]

參考資料

[1]

Free Code Camp - 解釋排序算法: https://www.freecodecamp.org/news/sorting-algorithms-explained/

[2]

Toptal - 排序算法動畫: https://www.toptal.com/developers/sorting-algorithms

[3]

在 JavaScript 中實現排序算法: https://medium.com/@rwillt/implementing-sorting-algorithms-in-javascript-b08504cdf4a9

[4]

andyhaskell: https://dev.to/andyhaskell

[5]

gogeof: https://github.com/gogeof

[6]

polaris1119: https://github.com/polaris1119

[7]

GCTT: https://github.com/studygolang/GCTT

[8]

Go 中文網: https://studygolang.com/

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/B6XxminkSJqCXZWC-Cm4uQ

猜你喜歡