在Go中如何進(jìn)行排序
排序操作在我們?nèi)粘ｉ_發(fā)中是經(jīng)常干的一件事，一些語言會(huì)提供開箱即用的工具，比如在 PHP 中關(guān)于數(shù)組對(duì)應(yīng)的?sort?函數(shù)。當(dāng)然在 Go 中也有對(duì)應(yīng)的實(shí)現(xiàn)方式。
介紹與使用
Go 中有一個(gè)?sort 內(nèi)置包，里面提供了一些排序函數(shù)用來對(duì)任何序列進(jìn)行排序操作。對(duì)于基礎(chǔ)的類型，直接提供了對(duì)應(yīng)的排序函數(shù)，比如下面展示的幾種類型的切片。
package mainimport ("fmt""sort")func main() {numbers := []int{18, 8, 28, 38}sort.Ints(numbers)fmt.Printf("int sort:%v\n", numbers)amounts := []float64{10, 1, 8.88, 2, 6}sort.Float64s(amounts)fmt.Printf("float64 sort:%v\n", amounts)strings := []string{"h", "e", "l", "l", "o"}sort.Strings(strings)??fmt.Printf("string?sort:%v\n",?strings)}
執(zhí)行這段代碼，可以看到各類型的切片已然有序。
當(dāng)然，不僅僅是切片，我們可以通過?sort.Sort()? 和? sort.Stable()?排序任意數(shù)據(jù)結(jié)構(gòu)。兩者最大的區(qū)別在于?sort.Sort()?不是穩(wěn)定排序，而?sort.Stable()?是穩(wěn)定排序。穩(wěn)定排序意味著對(duì)于相同的元素，能保證他們排序后和排序前的順序保持一致。
什么情況下可以調(diào)用這兩個(gè)函數(shù)？
只要是實(shí)現(xiàn)了?sort.Interface?接口的任意類型都可以使用這兩個(gè)函數(shù)進(jìn)行排序操作，至于原因，待會(huì)再解釋為什么。我們先來看?sort.Interface?接口。
主要包含三個(gè)方法。獲取結(jié)構(gòu)的長(zhǎng)度 Len()，元素比較返回的布爾值?Less()?以及交換兩個(gè)元素?Swap()，現(xiàn)在讓我們來實(shí)現(xiàn)它。
package mainimport ("fmt""sort")type UserInfo struct {Age intName string}type Users []UserInfofunc (users Users) Len() int { return len(users) }func?(users?Users)?Less(i,?j?int)?bool?{???//正序??return?users[i].Age?}func (users Users) Swap(i, j int) {users[i], users[j] = users[j], users[i]}func main() {userAll := []UserInfo{{20, "curry"},{18, "wuqinqiang"},{27, "張三"},{10, "李四"},{25, "王武"},}sort.Sort(Users(userAll))fmt.Println(userAll)}
我們定義了一個(gè)?UserInfo?的結(jié)構(gòu)體，Users?是一個(gè) UserInfo 結(jié)構(gòu)的切片。(注意：我們這里使用的是切片，但是不要把思維限制在切片上，?可以是實(shí)現(xiàn)了sort.Interface?接口的任意類型)。這里 Users?實(shí)現(xiàn)方法 Less()?是通過對(duì) age?的大小來實(shí)現(xiàn)正序排序。根據(jù)元素的比較結(jié)果然后使用 Swap()?來實(shí)現(xiàn)元素間的互換。
users[i],?users[j]?=?users[j],?users[i]元素間的互換可以通過以上的操作來進(jìn)行，這是 Go 的一些特性。當(dāng)然有些其他語言也支持。如果使用的是“世界上最好的語言”的話，那么要實(shí)現(xiàn)兩元素之間的互換，多數(shù)人會(huì)利用第三方變量，比如:
$a=1;$b=2;$temp=$a;$a=$b;$b=$temp;
有那味道了......。
以上介紹了Go 中 sort?包的一些使用姿勢(shì)?，F(xiàn)在我們開始稍微深入一點(diǎn)點(diǎn)了解一下底層原理。?
了解運(yùn)行原理
我們先進(jìn)入 sort.Sort()?方法。
// Sort sorts data.// It makes one call to data.Len to determine n, and O(n*log(n)) calls to// data.Less and data.Swap. The sort is not guaranteed to be stable.func Sort(data Interface) {n := data.Len()quickSort(data, 0, n, maxDepth(n))}
可以看到，首先會(huì)調(diào)用已經(jīng)實(shí)現(xiàn)的 Len()?計(jì)算長(zhǎng)度。然后調(diào)用了一個(gè)?quickSort()?(快速排序)的方法，在進(jìn)入這個(gè)方法之前，我們先看看? maxDepth(n)?函數(shù)是啥。
// maxDepth returns a threshold at which quicksort should switch// to heapsort. It returns 2*ceil(lg(n+1)).func maxDepth(n int) int { var depth intfor i := n; i > 0; i >>= 1 {depth++}return depth * 2}
從上面的解釋來看，此函數(shù)返回一個(gè)整形閥值，通過這個(gè)值來決定是選擇快排還是堆排。
這段代碼看起來有點(diǎn)蒙，要分成兩段來看:上面主要計(jì)算構(gòu)建完全二叉樹的深度，最后 *2 的意思是返回最深的完全二叉樹的深度。大佬的思路果然還是跟不上，emmm......
再回頭看 quickSort()?函數(shù)
func quickSort(data Interface, a, b, maxDepth int) {for b-a > 12 { // Use ShellSort for slices <= 12 elementsif maxDepth == 0 {heapSort(data, a, b)return}maxDepth--mlo, mhi := doPivot(data, a, b)// Avoiding recursion on the larger subproblem guarantees// a stack depth of at most lg(b-a).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)}}if b-a > 1 {// Do ShellSort pass with gap 6// It could be written in this simplified form cause b-a <= 12for i := a + 6; i < b; i++ {if data.Less(i, i-6) {data.Swap(i, i-6)}}insertionSort(data, a, b)}}
單看這段代碼還是好理解的，如果要比較的元素長(zhǎng)度大于 12，那么就在堆排序和快速排序之間做選擇。否則的話，就使用希爾排序和插入排序，可以看到希爾排序的間隔為 6。
這個(gè)快速排序方法中調(diào)用了?Swap()?和?Less()?方法，現(xiàn)在，再回頭看之前的 Less()，比較的規(guī)則是由你來決定的, sort.Sort()?會(huì)根據(jù)你定義的比較規(guī)則加上當(dāng)前的數(shù)量級(jí)來選擇相對(duì)應(yīng)的算法進(jìn)行規(guī)則排序。
這里還有一段代碼
func quickSort(data Interface, a, b, maxDepth int) {// .........................................................????mlo,?mhi?:=?doPivot(data,?a,?b)????// Avoiding recursion on the larger subproblem guarantees// a stack depth of at most lg(b-a).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)}??????//?....................}
實(shí)現(xiàn)快排的方式是遞歸，在獲取分區(qū)點(diǎn)的時(shí)候返回的是兩個(gè)值(多返回值是 Go 的特性)。但是代碼中，在返回分區(qū)點(diǎn)之后，并沒有進(jìn)行左右分區(qū)的遞歸查找，而是根據(jù)比較的結(jié)果，把數(shù)量多的一方放到下次循環(huán)中繼續(xù)切割，小的直接遞歸。
因?yàn)閷?shí)現(xiàn)的是遞歸，需要考慮到棧溢出的問題，這里也標(biāo)明調(diào)用?quickSort()?的最高棧深度為?log(b-a)，即 log(n)。
剩下的關(guān)于獲取分區(qū)點(diǎn)?doPivot()?方法的實(shí)現(xiàn)，感興趣的可以自己手摸手看。
再看搜索
既然已經(jīng)實(shí)現(xiàn)了排序，那么排序后咋么獲取指定元素所處的位置?? sort?包還提供了?Search?方法。下面是實(shí)現(xiàn):
func main() {userAll := []UserInfo{{20, "curry"},{18, "wuqinqiang"},{18, "測(cè)試2"},{27, "張三"},{10, "李四"},{25, "王武"},}sort.Sort(Users(userAll))temp:=18//搜索index := sort.Search(len(userAll), func(i int) bool {return userAll[i].Age >= temp})??//判斷元素是否存在if index < len(userAll) && userAll[index].Age == temp {fmt.Printf("元素:%d處于索引:%d處\n",temp,index)}else{fmt.Printf("元素:%d不存在\n",temp)}}
我們可以進(jìn)入 sort.Search()?查看，好吧，本質(zhì)上就是一個(gè)二分查找。
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, nfor i < j {??//獲取中位數(shù)h := int(uint(i+j) >> 1) // avoid overflow when computing h// i ≤ h < j????//這里的f?就是執(zhí)行我們傳進(jìn)來的????//func(i int) bool {// return userAll[i].Age >= temp?//? }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}
照著這里的邏輯，我們之前?age=18?，返回的是索引 1，假設(shè)我想返回的是相同值的最后一個(gè)索引處(對(duì)標(biāo) LeetCode34)，那么可以自己實(shí)現(xiàn)一個(gè)自定義的二分查找:
userAll := []UserInfo{{20, "curry"},{18, "wuqinqiang"},{18, "測(cè)試2"},{18, "測(cè)試3"},{18, "測(cè)試4"},{18, "測(cè)試5"},{18, "測(cè)試6"},{27, "張三"},{10, "李四"},{25, "王武"},}sort.Sort(Users(userAll))temp:=18index := SearchLast(len(userAll)-1, func(i int) bool {return userAll[i].Age <= temp})if index < len(userAll) && userAll[index].Age == temp {fmt.Printf("元素:%d處于索引:%d處\n",temp,index)}else{fmt.Printf("元素:%d不存在\n",temp)}}func SearchLast(n int, f func(int) bool) int {i, j := 0, nlast := -1for i <= j {h := int(uint(i+j) >> 1) // avoid overflow when computing hif f(h) {last, i = h, h+1} else {j = h - 1}}return last}
這篇文章到這里也就結(jié)束了，介紹了 sort?包一小部分的東西，還有很多東西我并未提到，一個(gè)是自己也還沒去用，另一個(gè)是有些東西，自己去發(fā)現(xiàn)更有樂趣。共勉。
推薦閱讀