golang 各种排序大比拼实例
1、准备工作
准备数据：
生成随机数并写入文件，之后在把数据读取出来
//新生成整数随机数，并存储在txt文件中，
funcNewIntRandm(fileNamestring,number,maxrandmint){
filename:=fileName
file,err:=os.Create(filename)
iferr!=nil{
return
}
r:=rand.New(rand.NewSource(time.Now().UnixNano()))
rans:=make([]string,0,number)
fori:=0;i
准备计时的程序：
packageutil
import"time"
typeStopwatchstruct{
starttime.Time
stoptime.Time
}
func(s*Stopwatch)Start(){
s.start=time.Now()
}
func(s*Stopwatch)Stop(){
s.stop=time.Now()
}
//纳秒
func(sStopwatch)RuntimeNs()int{
returns.stop.Nanosecond()-s.start.Nanosecond()
}
//微妙
func(sStopwatch)RuntimeUs()float64{
return(float64)(s.stop.Nanosecond()-s.start.Nanosecond())/1000.00
}
//毫秒
func(sStopwatch)RuntimeMs()float64{
return(float64)(s.stop.Nanosecond()-s.start.Nanosecond())/1000000.00
}
//秒
func(sStopwatch)RuntimeS()float64{
return(float64)(s.stop.Nanosecond()-s.start.Nanosecond())/10000000000.00
}
2、开始写排序
我模仿golang中的sort源码包中的写法，暴露了一个接口，把排序的实现都写在内部
packagesort
//packagemain
typeInterfaceinterface{
//获取数据的长度
Len()int
//判读索引为i和索引为j的值的大小，在实现的时候如果判断i>j返回true，则为升序，反之为降序
Less(i,jint)bool
//交换索引i，j的值
Swap(i,jint)
}
//冒泡排序
funcBubbleSort(dataInterface){
n:=data.Len()
forindex:=0;index0&&data.Less(j,j-1);j--{//j>0做一个边界守护，不让下标小于0
data.Swap(j,j-1)
}
}
}
//希尔排序
funcShellSort(dataInterface){
N:=data.Len()
h:=1
forh0{
forindex:=h;index=h&&data.Less(j,j-h);j-=h{//j>0做一个边界守护，不让下标小于0
data.Swap(j,j-h)
}
}
h=h/3
}
}
//快速排序
funcQuickSort(dataInterface){
n:=data.Len()
low,row:=0,n-1
quickSort(data,low,row)
}
funcquickSort(dataInterface,low,rowint){
iflow=1;i--{
data.Swap(0,i)
heapFixdown(data,0,i)
}
}
funcmakeHeap(dataInterface){
n:=data.Len()
fori:=(n-1)>>1;i>=0;i--{
heapFixdown(data,i,n)
}
}
funcheapFixdown(dataInterface,r,nint){
root:=r//跟结点
for{
leftChildIndex:=root<<1+1
ifleftChildIndex>=n{
break
}
ifleftChildIndex+1
3、开始使用
//先实现这个排序接口
typeInSort[]int
func(isInSort)Len()int{
returnlen(is)
}//降序
func(isInSort)Less(i,jint)bool{
returnis[i]>is[j]
}
func(isInSort)Swap(i,jint){
is[i],is[j]=is[j],is[i]
}
funcmain(){
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.8732ms
sort.QuickSort(insort)//开始排序，7.0267ms
t.Stop()
fmt.Println(t.RuntimeMs(),"ms")
util.SavaRandmInt("result.txt",insort)
}
快排：10000数组7.0267ms，1000000数组37.7612ms
堆排序：10000数组10.0039ms，1000000数组358.6429ms
下面是我测试的一些数据：
HeapSort(insort)//堆排序10000个数4.0013ms,100000个数54.0659ms,很稳定，500000个数208.1511ms很稳定
sort.QuickSort(insort,0,len(insort)-1)//快速排序10000个数3.0017ms,100000个数,33.0222ms,很稳定，500000个数150.1096ms很稳定,100000个数94.0823ms很稳定
sort.SelectSort(insort)//选择排序10000个数130.8017ms,100000个数时间很长
sort.BubbleSort(insort)//冒泡排序10000个数203.5344ms，100000个数187.7438ms
sort.InsertSrot(insort)//插入排序10000个数858.6085ms，100000个数,时间很长
sort.ShellSort(insort)//希尔插入10000个数10.9876ms，100000个数46.0322m，就做这个范围，很稳定，500000个数141.8833ms，相对稳定
sort.Sort(insort)//golang源码的排序10000个数6.0062ms，100000个数19.9988ms~89.0574ms不稳定,500000个数358.2536ms稳定
补充：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函数，funcTick(dDuration)<-chanTime
调用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
gotimerproc(tb)//如果还没有创建过管理定时任务的协程，则创建一个，执行通知管理timer的协程，最核心代码
}
}
timersBucket，顾名思义，时间任务桶，是外界不可见的全局变量。每当有新的timer定时器任务时，会将timer加入到timersBucket中的timer切片。
timerBucket结构体如下：
typetimersBucketstruct{
lockmutex//添加新定时任务时需要加锁（冲突点在于维护堆）
t[]*timer//timer切片，构造方式为四叉树最小堆
}
functimerproc(tb*timersBucket)详细介绍
可以称之为定时任务处理器，所有的定时任务都会加入timersBucket，然后在该函数中等待被处理。等待被处理的timer，根据when字段（任务执行的时间，int类型，纳秒级别）构成一个最小堆，每次处理完成堆顶的某个timer时，会给它的when字段加上定时任务循环间隔时间（即Tick(dDuration)中的d参数），然后重新维护堆，保证when最小的timer在堆顶。当堆中没有可以处理的timer(有timer,但是还不到执行时间)，需要计算当前时间和堆顶中timer的任务执行时间差值delta，定时任务处理器沉睡delta段时间，等待被调度器唤醒。核心代码如下（注释写在每行代码的后面，删除一些判断代码以及不利于阅读的非核心代码）：
functimerproc(tb*timersBucket){
for{
lock(&tb.lock)//加锁
now:=nanotime()//当前时间的纳秒值
delta:=int64(-1)//最近要执行的timer和当前时间的差值
for{
iflen(tb.t)==0{
delta=-1
break
}//当前无可执行timer,直接跳出该循环
t:=tb.t[0]
delta=t.when-now//取when组小的的timer，计算于当前时间的差值
ifdelta>0{
break
}//delta大于0，说明还未到发送channel时间，需要跳出循环去睡眠delta时间
ift.period>0{
//leaveinheapbutadjustnexttimetofire
t.when+=t.period*(1+-delta/t.period)//计算该timer下次执行任务的时间
siftdownTimer(tb.t,0)//调整堆
}else{
//removefromheap，如果没有设定下次执行时间，则将该timer从堆中移除（time.after和time.sleep函数即是只执行一次定时任务）
last:=len(tb.t)-1
iflast>0{
tb.t[0]=tb.t[last]
tb.t[0].i=0
}
tb.t[last]=nil
tb.t=tb.t[:last]
iflast>0{
siftdownTimer(tb.t,0)
}
t.i=-1//markasremoved
}
f:=t.f
arg:=t.arg
seq:=t.seq
unlock(&tb.lock)//解锁
f(arg,seq)//在channel中发送time结构体,唤醒阻塞的协程
lock(&tb.lock)
}
ifdelta<0{
//Notimersleft-putgoroutinetosleep.
goparkunlock(&tb.lock,"timergoroutine(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:linknametimeSleeptime.Sleep
functimeSleep(nsint64){
*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完成定时任务。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持毛票票。如有错误或未考虑完全的地方，望不吝赐教。