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 := root1 + 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完成定時任務。
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。如有錯誤或未考慮完全的地方，望不吝賜教。
您可能感興趣的文章:- golang/python實現(xiàn)歸并排序實例代碼
- Golang 實現(xiàn)插入排序的方法示例(2種)
- Golang實現(xiàn)拓撲排序(DFS算法版)
- golang對自定義類型進行排序的解決方法
- Golang算法問題之數(shù)組按指定規(guī)則排序的方法分析
- Golang正整數(shù)指定規(guī)則排序算法問題分析
