Go語(yǔ)言 排序與搜索切片

Go語(yǔ)言標(biāo)準(zhǔn)庫(kù)中提供了sort包對(duì)整型，浮點(diǎn)型，字符串型切片進(jìn)行排序，檢查一個(gè)切片是否排好序，使用二分法搜索函數(shù)在一個(gè)有序切片中搜索一個(gè)元素等功能。

創(chuàng)新互聯(lián)公司主營(yíng)濟(jì)水街道網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,重慶APP開(kāi)發(fā)公司,濟(jì)水街道h5微信平臺(tái)小程序開(kāi)發(fā)搭建,濟(jì)水街道網(wǎng)站營(yíng)銷推廣歡迎濟(jì)水街道等地區(qū)企業(yè)咨詢

關(guān)于sort包內(nèi)的函數(shù)說(shuō)明與使用，請(qǐng)查看

在這里簡(jiǎn)單講幾個(gè)sort包中常用的函數(shù)

在Go語(yǔ)言中，對(duì)字符串的排序都是按照字節(jié)排序，也就是說(shuō)在對(duì)字符串排序時(shí)是區(qū)分大小寫的。

二分搜索算法

Go語(yǔ)言中提供了一個(gè)使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比較㏒?n個(gè)元素，其中n為切片中元素的總數(shù)。

sort.Search(size,fn)函數(shù)接受兩個(gè)參數(shù)：所處理的切片的長(zhǎng)度和一個(gè)將目標(biāo)元素與有序切片的元素相比較的函數(shù)，該函數(shù)是一個(gè)閉包，如果該有序切片是升序排列，那么在判斷時(shí)使用 有序切片的元素 = 目標(biāo)元素。該函數(shù)返回一個(gè)int值，表示與目標(biāo)元素相同的切片元素的索引。

在切片中查找出某個(gè)與目標(biāo)字符串相同的元素索引

GoLang中的切片擴(kuò)容機(jī)制

[5]int 是數(shù)組，而 []int 是切片。二者看起來(lái)相似，實(shí)則是根本上不同的數(shù)據(jù)結(jié)構(gòu)。

切片的數(shù)據(jù)結(jié)構(gòu)中，包含一個(gè)指向數(shù)組的指針 array ，當(dāng)前長(zhǎng)度 len ，以及最大容量 cap 。在使用 make([]int, len) 創(chuàng)建切片時(shí)，實(shí)際上還有第三個(gè)可選參數(shù) cap ，也即 make([]int, len, cap) 。在不聲明 cap 的情況下，默認(rèn) cap=len 。當(dāng)切片長(zhǎng)度沒(méi)有超過(guò)容量時(shí)，對(duì)切片新增數(shù)據(jù)，不會(huì)改變 array 指針的值。

當(dāng)對(duì)切片進(jìn)行 append 操作，導(dǎo)致長(zhǎng)度超出容量時(shí)，就會(huì)創(chuàng)建新的數(shù)組，這會(huì)導(dǎo)致和原有切片的分離。在下例中

由于 a 的長(zhǎng)度超出了容量，所以切片 a 指向了一個(gè)增長(zhǎng)后的新數(shù)組，而 b 仍然指向原來(lái)的老數(shù)組。所以之后對(duì) a 進(jìn)行的操作，對(duì) b 不會(huì)產(chǎn)生影響。

試比較

本例中， a 的容量為6，因此在 append 后并未超出容量，所以 array 指針沒(méi)有改變。因此，對(duì) a 進(jìn)行的操作，對(duì) b 同樣產(chǎn)生了影響。

下面看看用 a := []int{} 這種方式來(lái)創(chuàng)建切片會(huì)是什么情況。

可以看到，空切片的容量為0，但后面向切片中添加元素時(shí)，并不是每次切片的容量都發(fā)生了變化。這是因?yàn)?，如果增大容量，也即需要?jiǎng)?chuàng)建新數(shù)組，這時(shí)還需要將原數(shù)組中的所有元素復(fù)制到新數(shù)組中，開(kāi)銷很大，所以GoLang設(shè)計(jì)了一套擴(kuò)容機(jī)制，以減少需要?jiǎng)?chuàng)建新數(shù)組的次數(shù)。但這導(dǎo)致無(wú)法很直接地判斷 append 時(shí)是否創(chuàng)建了新數(shù)組。

如果一次添加多個(gè)元素，容量又會(huì)怎樣變化呢？試比較下面兩個(gè)例子：

那么，是不是說(shuō)，當(dāng)向一個(gè)空切片中插入 2n-1 個(gè)元素時(shí)，容量就會(huì)被設(shè)置為 2n 呢？我們來(lái)試試其他的數(shù)據(jù)類型。

可以看到，根據(jù)切片對(duì)應(yīng)數(shù)據(jù)類型的不同，容量增長(zhǎng)的方式也有很大的區(qū)別。相關(guān)的源碼包括： src/runtime/msize.go ， src/runtime/mksizeclasses.go 等。

我們?cè)倏纯辞衅跏挤强盏那樾巍?/p>

可以看到，與剛剛向空切片添加5個(gè)int的情況一致，向有3個(gè)int的切片中添加2個(gè)int，容量增長(zhǎng)為6。

需要注意的是， append 對(duì)切片擴(kuò)容時(shí)，如果容量超過(guò)了一定范圍，處理策略又會(huì)有所不同?？梢钥纯聪旅孢@個(gè)例子。

具體為什么會(huì)是這樣的變化過(guò)程，還需要從 源碼 中尋找答案。下面是 src/runtime/slice.go 中的 growslice 函數(shù)中的核心部分。

GoLang中的切片擴(kuò)容機(jī)制，與切片的數(shù)據(jù)類型、原本切片的容量、所需要的容量都有關(guān)系，比較復(fù)雜。對(duì)于常見(jiàn)數(shù)據(jù)類型，在元素?cái)?shù)量較少時(shí)，大致可以認(rèn)為擴(kuò)容是按照翻倍進(jìn)行的。但具體情況需要具體分析。

go語(yǔ)言中實(shí)現(xiàn)切片(slice)的三種方式

定義一個(gè)切片，然后讓切片去引用一個(gè)已經(jīng)創(chuàng)建好的數(shù)組?；菊Z(yǔ)法如下：

索引1：切片引用的起始元素位

索引2：切片只引用該元素位之前的元素

例程如下：

在該方法中，我們未指定容量cap，這里的值為5是系統(tǒng)定義的。

在方法一中，可以用arr數(shù)組名來(lái)操控?cái)?shù)組中的元素，也可以通過(guò)slice切片來(lái)操控?cái)?shù)組中的元素。切片是直接引用數(shù)組，數(shù)組是事先存在的，程序員是可見(jiàn)的。

通過(guò) make 來(lái)創(chuàng)建切片，基本語(yǔ)法如下：

make函數(shù)第三個(gè)參數(shù)cap即容量是可選的，如果一定要自己注明的話，要注意保證cap≥len。

用該方法可以 指定切片的大小(len)和容量(cap)

例程如下：

由于未賦值系統(tǒng)默認(rèn)將元素值置為0，即：

數(shù)值類型數(shù)組：????默認(rèn)值為 0

字符串?dāng)?shù)組：? ? ? ?默認(rèn)值為 ""

bool數(shù)組：? ? ? ? ? ?默認(rèn)值為 false

在方法二中，通過(guò)make方式創(chuàng)建的切片對(duì)應(yīng)的數(shù)組是由make底層維護(hù)，對(duì)外不可見(jiàn)，即只能通過(guò)slice去訪問(wèn)各個(gè)元素。

定義一個(gè)切片，直接就指定具體數(shù)組，使用原理類似于make的方式。

例程如下：