golang 各種排序大比拼實例
1、準備工作
準備數(shù)據(jù)：
生成隨機數(shù)并寫入文件，之后在把數(shù)據(jù)讀取出來
//新生成整數(shù)隨機數(shù)，并存儲在txt文件中，
func NewIntRandm(fileName string, number, maxrandm int) {
filename := fileName
file, err := os.Create(filename)
if err != nil {
return
}
r := rand.New(rand.NewSource(time.Now().UnixNano()))
rans := make([]string, 0, number)
for i := 0; i < number; i++ {
rans = append(rans, strconv.Itoa(r.Intn(maxrandm)))
}
file.WriteString(strings.Join(rans, " "))
defer file.Close()
}
//把一串數(shù)組存入文件總
func SavaRandmInt(fileName string, data []int) {
if fileName == " " || len(data) == 0 {
return
}
var file *os.File
var openerr error
file, openerr = os.Open(fileName)
if openerr != nil {
var newerr error
file, newerr = os.Create(fileName)
if newerr != nil {
return
}
}
rans := make([]string, 0, len(data))
for _, v := range data {
rans = append(rans, strconv.Itoa(v))
}
file.WriteString(strings.Join(rans, " "))
defer file.Close()
}
準備計時的程序：
package util
import "time"
type Stopwatch struct {
start time.Time
stop time.Time
}
func (s *Stopwatch) Start() {
s.start = time.Now()
}
func (s *Stopwatch) Stop() {
s.stop = time.Now()
}
//納秒
func (s Stopwatch) RuntimeNs() int {
return s.stop.Nanosecond() - s.start.Nanosecond()
}
//微妙
func (s Stopwatch) RuntimeUs() float64 {
return (float64)(s.stop.Nanosecond()-s.start.Nanosecond()) / 1000.00
}
//毫秒
func (s Stopwatch) RuntimeMs() float64 {
return (float64)(s.stop.Nanosecond()-s.start.Nanosecond()) / 1000000.00
}
//秒
func (s Stopwatch) RuntimeS() float64 {
return (float64)(s.stop.Nanosecond()-s.start.Nanosecond()) / 10000000000.00
}
2、開始寫排序
我模仿golang中的sort源碼包中的寫法，暴露了一個接口，把排序的實現(xiàn)都寫在內部
package sort
// package main
type Interface interface {
//獲取數(shù)據(jù)的長度
Len() int
//判讀索引為i和索引為j的值的大小，在實現(xiàn)的時候如果判斷i>j 返回true，則為升序，反之為降序
Less(i, j int) bool
//交換索引i，j的值
Swap(i, j int)
}
//冒泡排序
func BubbleSort(data Interface) {
n := data.Len()
for index := 0; index < n; index++ {
for j := index + 1; j < n; j++ {
if data.Less(index, j) {
data.Swap(index, j)
}
}
}
}
//此方法比上面的冒泡算法快，因為我找最小元素是指記住下標，并沒有每一次都做元素交換
func SelectSort(data Interface) {
n := data.Len()
var min int
for index := 0; index < n; index++ {
min = index
for j := index + 1; j < n; j++ {
if data.Less(min, j) {
min = j
}
}
data.Swap(index, min)
}
}
//插入排序
func InsertSrot(data Interface) {
count := data.Len()
for index := 1; index < count; index++ {
for j := index; j > 0 && data.Less(j, j-1); j-- { //j>0 做一個邊界守護，不讓下標小于0
data.Swap(j, j-1)
}
}
}
//希爾排序
func ShellSort(data Interface) {
N := data.Len()
h := 1
for h < N/3 {
h = 3*h + 1
}
for h > 0 {
for index := h; index < N; index++ {
for j := index; j >= h && data.Less(j, j-h); j -= h { //j>0 做一個邊界守護，不讓下標小于0
data.Swap(j, j-h)
}
}
h = h / 3
}
}
//快速排序
func QuickSort(data Interface) {
n := data.Len()
low, row := 0, n-1
quickSort(data, low, row)
}
func quickSort(data Interface, low, row int) {
if low < row {
i, j, x, last := low, row, low, 0 //0就是使用第一個作為基準值,last這個變量時為了基準最后一次交換變量時出現(xiàn)在那次
for i < j {
for i < j && data.Less(x, j) { //比x小的放在前面出現(xiàn)的坑中
j--
}
if i < j {
data.Swap(i, j)
i++
x = j
last = 1
}
for i < j && data.Less(i, x) { //比x大的放在后面出現(xiàn)的坑中
i++
}
if i < j {
data.Swap(i, j)
j--
x = i
last = -1
}
}
if last == 1 {
data.Swap(j, x)
} else if last == -1 {
data.Swap(i, x)
}
quickSort(data, low, i-1)
quickSort(data, i+1, row)
}
}
//通過控制Less方法來控制升序降序
func HeapSort(data Interface) {
makeHeap(data)
n := data.Len()
for i := n - 1; i >= 1; i-- {
data.Swap(0, i)
heapFixdown(data, 0, i)
}
}
func makeHeap(data Interface) {
n := data.Len()
for i := (n - 1) >> 1; i >= 0; i-- {
heapFixdown(data, i, n)
}
}
func heapFixdown(data Interface, r, n int) {
root := r //跟結點
for {
leftChildIndex := root<<1 + 1
if leftChildIndex >= n {
break
}
if leftChildIndex+1 < n && data.Less(leftChildIndex+1, leftChildIndex) {
leftChildIndex++
}
if data.Less(root, leftChildIndex) {
return
}
data.Swap(leftChildIndex, root)
root = leftChildIndex
}
}
3、開始使用
//先實現(xiàn)這個排序接口
type InSort []int
func (is InSort) Len() int {
return len(is)
}//降序
func (is InSort) Less(i, j int) bool {
return is[i] > is[j]
}
func (is InSort) Swap(i, j int) {
is[i], is[j] = is[j], is[i]
}
func main() {
fileName := "randm.txt"
// util.NewIntRandm(fileName, 1000000, 10000) //封裝生成5000000個隨機數(shù)字
fileUtil := util.FileUtil{}
insort := InSort{}
insort = fileUtil.ReaderAllInt(fileName) //讀取生成的隨機數(shù)
fmt.Println(insort.Len())
t := new(util.Stopwatch) //封裝的計時間的方法
t.Start()
// sort.HeapSort(insort) //開始排序，519.8732 ms
sort.QuickSort(insort) //開始排序，7.0267 ms
t.Stop()
fmt.Println(t.RuntimeMs(), "ms")
util.SavaRandmInt("result.txt", insort)
}
快排：10000數(shù)組 7.0267 ms，1000000數(shù)組 37.7612 ms
堆排序：10000數(shù)組 10.0039 ms，1000000數(shù)組 358.6429 ms
下面是我測試的一些數(shù)據(jù)：
HeapSort(insort) //堆排序 10000個數(shù) 4.0013 ms,100000個數(shù) 54.0659 ms,很穩(wěn)定，500000個數(shù) 208.1511 ms 很穩(wěn)定 sort.QuickSort(insort, 0, len(insort)-1) //快速排序 10000個數(shù) 3.0017 ms,100000個數(shù),33.0222 ms,很穩(wěn)定，500000個數(shù) 150.1096 ms 很穩(wěn)定,100000個數(shù) 94.0823 ms 很穩(wěn)定 sort.SelectSort(insort) //選擇排序 10000個數(shù) 130.8017 ms,100000個數(shù) 時間很長 sort.BubbleSort(insort) //冒泡排序 10000個數(shù) 203.5344ms ，100000個數(shù) 187.7438 ms sort.InsertSrot(insort) // 插入排序 10000個數(shù) 858.6085 ms，100000個數(shù),時間很長 sort.ShellSort(insort) //希爾插入 10000個數(shù) 10.9876 ms，100000個數(shù) 46.0322 m ，就做這個范圍，很穩(wěn)定，500000個數(shù) 141.8833 ms，相對穩(wěn)定 sort.Sort(insort) //golang源碼的排序 10000個數(shù) 6.0062 ms ，100000個數(shù) 19.9988 ms~89.0574 ms 不穩(wěn)定,500000個數(shù) 358.2536 ms 穩(wěn)定
補充：golang 定時任務方面time.Sleep和time.Tick的優(yōu)劣對比
golang 寫循環(huán)執(zhí)行的定時任務，常見的有以下三種實現(xiàn)方式:
1、time.Sleep方法：
for {
time.Sleep(time.Second)
fmt.Println("我在定時執(zhí)行任務")
}
2、time.Tick函數(shù)：
t1:=time.Tick(3*time.Second)
for {
select {
case <-t1:
fmt.Println("t1定時器")
}
}
3、其中Tick定時任務，也可以先使用time.Ticker函數(shù)獲取Ticker結構體，然后進行阻塞監(jiān)聽信息，這種方式可以手動選擇停止定時任務，在停止任務時，減少對內存的浪費。
t:=time.NewTicker(time.Second)
for {
select {
case <-t.C:
fmt.Println("t1定時器")
t.Stop()
}
}
其中第二種和第三種可以歸為同一類
這三種定時器的實現(xiàn)原理
一般來說，你在使用執(zhí)行定時任務的時候，一般旁人會勸你不要使用time.Sleep完成定時任務，但是為什么不能使用Sleep函數(shù)完成定時任務呢，它和Tick函數(shù)比，有什么劣勢呢？這就需要我們去探討閱讀一下源碼，分析一下它們之間的優(yōu)劣性。
首先，我們研究一下Tick函數(shù)，func Tick(d Duration) <-chan Time
調用Tick函數(shù)會返回一個時間類型的channel，如果對channel稍微有些了解的話，我們首先會想到，既然是返回一個channel，在調用Tick方法的過程中，必然創(chuàng)建了goroutine,該Goroutine負責發(fā)送數(shù)據(jù)，喚醒被阻塞的定時任務。我在閱讀源碼之后，確實發(fā)現(xiàn)函數(shù)中go出去了一個協(xié)程，處理定時任務。
按照當前的理解，使用一個tick,需要go出去一個協(xié)程，效率和對內存空間的占用肯定不能比sleep函數(shù)強。我們需要繼續(xù)閱讀源碼才拿獲取到真理。
簡單的調用過程我就不陳述了，我在這介紹一下核心結構體和方法（刪除了部分判斷代碼，解釋我寫在表格中）：
func (tb *timersBucket) addtimerLocked(t *timer) {
t.i = len(tb.t) //計算timersBucket中，當前定時任務的長度
tb.t = append(tb.t, t)// 將當前定時任務加入timersBucket
siftupTimer(tb.t, t.i) //維護一個timer結構體的最小堆（四叉樹），排序關鍵字為執(zhí)行時間，即該定時任務下一次執(zhí)行的時間
if !tb.created {
tb.created = true
go timerproc(tb)// 如果還沒有創(chuàng)建過管理定時任務的協(xié)程，則創(chuàng)建一個，執(zhí)行通知管理timer的協(xié)程，最核心代碼
}
}
timersBucket，顧名思義，時間任務桶，是外界不可見的全局變量。每當有新的timer定時器任務時，會將timer加入到timersBucket中的timer切片。
timerBucket結構體如下：
type timersBucket struct {
lock mutex //添加新定時任務時需要加鎖（沖突點在于維護堆）
t []*timer //timer切片，構造方式為四叉樹最小堆
}
func timerproc(tb *timersBucket) 詳細介紹
可以稱之為定時任務處理器，所有的定時任務都會加入timersBucket，然后在該函數(shù)中等待被處理。等待被處理的timer，根據(jù)when字段（任務執(zhí)行的時間，int類型，納秒級別）構成一個最小堆，每次處理完成堆頂?shù)哪硞€timer時，會給它的when字段加上定時任務循環(huán)間隔時間（即Tick(d Duration) 中的d參數(shù)），然后重新維護堆，保證when最小的timer在堆頂。當堆中沒有可以處理的timer(有timer,但是還不到執(zhí)行時間)，需要計算當前時間和堆頂中timer的任務執(zhí)行時間差值delta，定時任務處理器沉睡delta段時間，等待被調度器喚醒。核心代碼如下（注釋寫在每行代碼的后面，刪除一些判斷代碼以及不利于閱讀的非核心代碼）：
func timerproc(tb *timersBucket) {
for {
lock(&tb.lock) //加鎖
now := nanotime() //當前時間的納秒值
delta := int64(-1) //最近要執(zhí)行的timer和當前時間的差值
for {
if len(tb.t) == 0 {
delta = -1
break
}//當前無可執(zhí)行timer,直接跳出該循環(huán)
t := tb.t[0]
delta = t.when - now //取when組小的的timer，計算于當前時間的差值
if delta > 0 {
break
}// delta大于0，說明還未到發(fā)送channel時間，需要跳出循環(huán)去睡眠delta時間
if t.period > 0 {
// leave in heap but adjust next time to fire
t.when += t.period * (1 + -delta/t.period)// 計算該timer下次執(zhí)行任務的時間
siftdownTimer(tb.t, 0) //調整堆
} else {
// remove from heap，如果沒有設定下次執(zhí)行時間，則將該timer從堆中移除（time.after和time.sleep函數(shù)即是只執(zhí)行一次定時任務）
last := len(tb.t) - 1
if last > 0 {
tb.t[0] = tb.t[last]
tb.t[0].i = 0
}
tb.t[last] = nil
tb.t = tb.t[:last]
if last > 0 {
siftdownTimer(tb.t, 0)
}
t.i = -1 // mark as removed
}
f := t.f
arg := t.arg
seq := t.seq
unlock(&tb.lock)//解鎖
f(arg, seq) //在channel中發(fā)送time結構體,喚醒阻塞的協(xié)程
lock(&tb.lock)
}
if delta < 0 {
// No timers left - put goroutine to sleep.
goparkunlock(&tb.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
continue
}// delta小于0說明當前無定時任務，直接進行阻塞進行睡眠
tb.sleeping = true
tb.sleepUntil = now + delta
unlock(&tb.lock)
notetsleepg(&tb.waitnote, delta) //睡眠delta時間，喚醒之后就可以執(zhí)行在堆頂?shù)亩〞r任務了
}
}
至此，time.Tick函數(shù)涉及到的主要功能就講解結束了，總結一下就是啟動定時任務時，會創(chuàng)建一個唯一協(xié)程，處理timer,所有的timer都在該協(xié)程中處理。
然后，我們再閱讀一下sleep的源碼實現(xiàn)，核心源碼如下：
//go:linkname timeSleep time.Sleep
func timeSleep(ns int64) {
*t = timer{} //創(chuàng)建一個定時任務
t.when = nanotime() + ns //計算定時任務的執(zhí)行時間點
t.f = goroutineReady //執(zhí)行方法
tb.addtimerLocked(t) //加入timer堆，并在timer定時任務執(zhí)行協(xié)程中等待被執(zhí)行
goparkunlock(&tb.lock, "sleep", traceEvGoSleep, 2) //睡眠，等待定時任務協(xié)程通知喚醒
}
讀了sleep的核心代碼之后，是不是突然發(fā)現(xiàn)和Tick函數(shù)的內容很類似，都創(chuàng)建了timer,并加入了定時任務處理協(xié)程。神奇之處就在于，實際上這兩個函數(shù)產生的timer都放入了同一個timer堆，都在定時任務處理協(xié)程中等待被處理。
優(yōu)劣性對比，使用建議
現(xiàn)在我們知道了，Tick，Sleep，包括time.After函數(shù)，都使用的timer結構體，都會被放在同一個協(xié)程中統(tǒng)一處理，這樣看起來使用Tick，Sleep并沒有什么區(qū)別。
實際上是有區(qū)別的，Sleep是使用睡眠完成定時任務，需要被調度喚醒。Tick函數(shù)是使用channel阻塞當前協(xié)程，完成定時任務的執(zhí)行。當前并不清楚golang 阻塞和睡眠對資源的消耗會有什么區(qū)別，這方面不能給出建議。
但是使用channel阻塞協(xié)程完成定時任務比較靈活，可以結合select設置超時時間以及默認執(zhí)行方法，而且可以設置timer的主動關閉，以及不需要每次都生成一個timer(這方面節(jié)省系統(tǒng)內存，垃圾收回也需要時間)。
所以，建議使用time.Tick完成定時任務。
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。如有錯誤或未考慮完全的地方，望不吝賜教。
相關文章
這篇文章主要為大家詳細介紹了如何使用Go語言構建WebSocket服務器和客戶端,以實現(xiàn)雙向通信,文中的示例代碼講解詳細,需要的小伙伴可以參考一下2023-11-11
這篇文章主要為大家介紹了從錯誤中學習改正Go語言五個壞習慣提高編程技巧示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
訪問者是一種行為設計模式, 允許你在不修改已有代碼的情況下向已有類層次結構中增加新的行為,本文將通過代碼示例給大家詳細的介紹一下Go設計模式之訪問者模式,需要的朋友可以參考下2023-08-08
這篇文章主要為大家介紹了如何使用Nunu快速構建高效可靠Go應用腳手架詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-06-06
串口通信是一種常見的硬件通信方式,用于在計算機和外部設備之間傳輸數(shù)據(jù),本文主要介紹了Golang 串口通信的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下2024-03-03
數(shù)據(jù)庫在存儲密碼時，不能明文存儲，需要加密后存儲，而Golang中的加密算法有很多種，下面小編就來通過簡單的示例和大家簡單聊聊吧2023-07-07
本文主要介紹了Golang交叉編譯(跨平臺編譯)的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
詳解golang開發(fā)中http請求redirect的問題
這篇文章主要介紹了詳解golang開發(fā)中http請求redirect的問題，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10
Golang無限緩存channel的設計與實現(xiàn)解析
這篇文章主要為大家介紹了Golang無限緩存channel的設計與實現(xiàn)解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
冒泡排序算法是數(shù)據(jù)結構中常用的一種算法，本文就介紹了go實現(xiàn)冒泡排序算法，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03