golang 各種排序大比拼實例
1、準備工作
準備數據：
生成隨機數並寫入文件，之後在把數據讀取出來
//新生成整數隨機數，並存儲在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()
}
//把一串數組存入文件總
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源碼包中的寫法，暴露瞭一個接口，把排序的實現都寫在內部
package sort
// package main
type Interface interface {
//獲取數據的長度
Len() int
//判讀索引為i和索引為j的值的大小，在實現的時候如果判斷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這個變量時為瞭基準最後一次交換變量時出現在那次
for i < j {
for i < j && data.Less(x, j) { //比x小的放在前面出現的坑中
j--
}
if i < j {
data.Swap(i, j)
i++
x = j
last = 1
}
for i < j && data.Less(i, x) { //比x大的放在後面出現的坑中
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、開始使用
//先實現這個排序接口
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個隨機數字
fileUtil := util.FileUtil{}
insort := InSort{}
insort = fileUtil.ReaderAllInt(fileName) //讀取生成的隨機數
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數組 7.0267 ms，1000000數組 37.7612 ms
堆排序：10000數組 10.0039 ms，1000000數組 358.6429 ms
下面是我測試的一些數據：
HeapSort(insort) //堆排序 10000個數 4.0013 ms,100000個數 54.0659 ms,很穩定，500000個數 208.1511 ms 很穩定 sort.QuickSort(insort, 0, len(insort)-1) //快速排序 10000個數 3.0017 ms,100000個數,33.0222 ms,很穩定，500000個數 150.1096 ms 很穩定,100000個數 94.0823 ms 很穩定 sort.SelectSort(insort) //選擇排序 10000個數 130.8017 ms,100000個數 時間很長 sort.BubbleSort(insort) //冒泡排序 10000個數 203.5344ms ，100000個數 187.7438 ms sort.InsertSrot(insort) // 插入排序 10000個數 858.6085 ms，100000個數,時間很長 sort.ShellSort(insort) //希爾插入 10000個數 10.9876 ms，100000個數 46.0322 m ，就做這個范圍，很穩定，500000個數 141.8833 ms，相對穩定 sort.Sort(insort) //golang源碼的排序 10000個數 6.0062 ms ，100000個數 19.9988 ms~89.0574 ms 不穩定,500000個數 358.2536 ms 穩定
補充：golang 定時任務方面time.Sleep和time.Tick的優劣對比
golang 寫循環執行的定時任務，常見的有以下三種實現方式:
1、time.Sleep方法：
for {
time.Sleep(time.Second)
fmt.Println("我在定時執行任務")
}
2、time.Tick函數：
t1:=time.Tick(3*time.Second)
for {
select {
case <-t1:
fmt.Println("t1定時器")
}
}
3、其中Tick定時任務，也可以先使用time.Ticker函數獲取Ticker結構體，然後進行阻塞監聽信息，這種方式可以手動選擇停止定時任務，在停止任務時，減少對內存的浪費。
t:=time.NewTicker(time.Second)
for {
select {
case <-t.C:
fmt.Println("t1定時器")
t.Stop()
}
}
其中第二種和第三種可以歸為同一類
這三種定時器的實現原理
一般來說，你在使用執行定時任務的時候，一般旁人會勸你不要使用time.Sleep完成定時任務，但是為什麼不能使用Sleep函數完成定時任務呢，它和Tick函數比，有什麼劣勢呢？這就需要我們去探討閱讀一下源碼，分析一下它們之間的優劣性。
首先，我們研究一下Tick函數，func Tick(d Duration) <-chan Time
調用Tick函數會返回一個時間類型的channel，如果對channel稍微有些瞭解的話，我們首先會想到，既然是返回一個channel，在調用Tick方法的過程中，必然創建瞭goroutine,該Goroutine負責發送數據，喚醒被阻塞的定時任務。我在閱讀源碼之後，確實發現函數中go出去瞭一個協程，處理定時任務。
按照當前的理解，使用一個tick,需要go出去一個協程，效率和對內存空間的占用肯定不能比sleep函數強。我們需要繼續閱讀源碼才拿獲取到真理。
簡單的調用過程我就不陳述瞭，我在這介紹一下核心結構體和方法（刪除瞭部分判斷代碼，解釋我寫在表格中）：
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結構體的最小堆（四叉樹），排序關鍵字為執行時間，即該定時任務下一次執行的時間
if !tb.created {
tb.created = true
go timerproc(tb)// 如果還沒有創建過管理定時任務的協程，則創建一個，執行通知管理timer的協程，最核心代碼
}
}
timersBucket，顧名思義，時間任務桶，是外界不可見的全局變量。每當有新的timer定時器任務時，會將timer加入到timersBucket中的timer切片。
timerBucket結構體如下：
type timersBucket struct {
lock mutex //添加新定時任務時需要加鎖（沖突點在於維護堆）
t []*timer //timer切片，構造方式為四叉樹最小堆
}
func timerproc(tb *timersBucket) 詳細介紹
可以稱之為定時任務處理器，所有的定時任務都會加入timersBucket，然後在該函數中等待被處理。等待被處理的timer，根據when字段（任務執行的時間，int類型，納秒級別）構成一個最小堆，每次處理完成堆頂的某個timer時，會給它的when字段加上定時任務循環間隔時間（即Tick(d Duration) 中的d參數），然後重新維護堆，保證when最小的timer在堆頂。當堆中沒有可以處理的timer(有timer,但是還不到執行時間)，需要計算當前時間和堆頂中timer的任務執行時間差值delta，定時任務處理器沉睡delta段時間，等待被調度器喚醒。核心代碼如下（註釋寫在每行代碼的後面，刪除一些判斷代碼以及不利於閱讀的非核心代碼）：
func timerproc(tb *timersBucket) {
for {
lock(&tb.lock) //加鎖
now := nanotime() //當前時間的納秒值
delta := int64(-1) //最近要執行的timer和當前時間的差值
for {
if len(tb.t) == 0 {
delta = -1
break
}//當前無可執行timer,直接跳出該循環
t := tb.t[0]
delta = t.when - now //取when組小的的timer，計算於當前時間的差值
if delta > 0 {
break
}// delta大於0，說明還未到發送channel時間，需要跳出循環去睡眠delta時間
if t.period > 0 {
// leave in heap but adjust next time to fire
t.when += t.period * (1 + -delta/t.period)// 計算該timer下次執行任務的時間
siftdownTimer(tb.t, 0) //調整堆
} else {
// remove from heap，如果沒有設定下次執行時間，則將該timer從堆中移除（time.after和time.sleep函數即是隻執行一次定時任務）
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中發送time結構體,喚醒阻塞的協程
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時間，喚醒之後就可以執行在堆頂的定時任務瞭
}
}
至此，time.Tick函數涉及到的主要功能就講解結束瞭，總結一下就是啟動定時任務時，會創建一個唯一協程，處理timer,所有的timer都在該協程中處理。
然後，我們再閱讀一下sleep的源碼實現，核心源碼如下：
//go:linkname timeSleep time.Sleep
func timeSleep(ns int64) {
*t = timer{} //創建一個定時任務
t.when = nanotime() + ns //計算定時任務的執行時間點
t.f = goroutineReady //執行方法
tb.addtimerLocked(t) //加入timer堆，並在timer定時任務執行協程中等待被執行
goparkunlock(&tb.lock, "sleep", traceEvGoSleep, 2) //睡眠，等待定時任務協程通知喚醒
}
讀瞭sleep的核心代碼之後，是不是突然發現和Tick函數的內容很類似，都創建瞭timer,並加入瞭定時任務處理協程。神奇之處就在於，實際上這兩個函數產生的timer都放入瞭同一個timer堆，都在定時任務處理協程中等待被處理。
優劣性對比，使用建議
現在我們知道瞭，Tick，Sleep，包括time.After函數，都使用的timer結構體，都會被放在同一個協程中統一處理，這樣看起來使用Tick，Sleep並沒有什麼區別。
實際上是有區別的，Sleep是使用睡眠完成定時任務，需要被調度喚醒。Tick函數是使用channel阻塞當前協程，完成定時任務的執行。當前並不清楚golang 阻塞和睡眠對資源的消耗會有什麼區別，這方面不能給出建議。
但是使用channel阻塞協程完成定時任務比較靈活，可以結合select設置超時時間以及默認執行方法，而且可以設置timer的主動關閉，以及不需要每次都生成一個timer(這方面節省系統內存，垃圾收回也需要時間)。
所以，建議使用time.Tick完成定時任務。
以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方，望不吝賜教。
推薦閱讀：
- golang 定時任務方面time.Sleep和time.Tick的優劣對比分析
- Golang定時器Timer與Ticker的使用詳解
- Golang 定時器的終止與重置實現
- 淺談golang 中time.After釋放的問題
- golang編程開發使用sort排序示例詳解