Go之十大经典排序算法

本文内容纲要：

1.冒泡排序

funcbubble_sort(li[]int){ fori:=0;i<len(li)-1;i++{ exchange:=false forj:=0;j<len(li)-i-1;j++{ ifli[j]>li[j+1]{ li[j],li[j+1]=li[j+1],li[j] exchange=true } } if!exchange{ return } } }

2.选择排序

funcselect_sort(li[]int){ fori:=0;i<len(li)-1;i++{ pos:=i forj:=i+1;j<len(li);j++{ ifli[pos]>li[j]{ pos=j } } li[i],li[pos]=li[pos],li[i] } }

3.插入排序

funcinsert_sort(li[]int){ fori:=1;i<len(li);i++{ tmp:=li[i] j:=i-1 forj>=0&&tmp<li[j]{ li[j+1]=li[j] j-- } li[j+1]=tmp } }

4.希尔排序

funcshell_sort(li[]int){ forgap:=len(li)/2;gap>0;gap/=2{ fori:=gap;i<len(li);i++{ tmp:=li[i] j:=i-gap forj>=0&&tmp<li[j]{ li[j+gap]=li[j] j-=gap } li[j+gap]=tmp } } }

5.快速排序

funcquick_sort(li[]int,left,rightint){ ifleft>=right{ return } i:=left j:=right rand.Seed(time.Now().Unix()) r:=rand.Intn(right-left)+left li[i],li[r]=li[r],li[i] tmp:=li[i] fori<j{ fori<j&&li[j]>=tmp{ j-- } li[i]=li[j] fori<j&&li[i]<=tmp{ i++ } li[j]=li[i] } li[i]=tmp quick_sort(li,left,i-1) quick_sort(li,i+1,right) }

6.堆排序

funcsift(li[]int,low,highint){ i:=low j:=2*i+1 tmp:=li[i] forj<=high{ ifj<high&&li[j]<li[j+1]{ j++ } iftmp<li[j]{ li[i]=li[j] i=j j=2*i+1 }else{ break } } li[i]=tmp } funcheap_sort(li[]int){ fori:=len(li)/2-1;i>=0;i--{ sift(li,i,len(li)-1) } forj:=len(li)-1;j>0;j--{ li[0],li[j]=li[j],li[0] sift(li,0,j-1) } }

7.归并排序

funcmerge(li[]int,left,mid,rightint){ i:=left j:=mid+1 tmp:=[]int{} fori<=mid&&j<=right{ ifli[i]<=li[j]{ tmp=append(tmp,li[i]) i++ }else{ tmp=append(tmp,li[j]) j++ } } ifi<=mid{ tmp=append(tmp,li[i:mid+1]...) }else{ tmp=append(tmp,li[j:right+1]...) } fork:=0;k<len(tmp);k++{ li[left+k]=tmp[k] } } funcmerge_sort(li[]int,left,rightint){ ifleft<right{ mid:=(left+right)/2 merge_sort(li,left,mid) merge_sort(li,mid+1,right) merge(li,left,mid,right) } }

8.计数排序

funccount_sort(li[]int){ max_num:=li[0] fori:=1;i<len(li);i++{ ifmax_num<li[i]{ max_num=li[i] } } arr:=make([]int,max_num+1) forj:=0;j<len(li);j++{ arr[li[j]]++ } k:=0 form,n:=rangearr{ forp:=0;p<n;p++{ li[k]=m k++ } } }

9.桶排序

funcbin_sort(li[]int,bin_numint){ min_num,max_num:=li[0],li[0] fori:=0;i<len(li);i++{ ifmin_num>li[i]{ min_num=li[i] } ifmax_num<li[i]{ max_num=li[i] } } bin:=make([][]int,bin_num) forj:=0;j<len(li);j++{ n:=(li[j]-min_num)/((max_num-min_num+1)/bin_num) bin[n]=append(bin[n],li[j]) k:=len(bin[n])-2 fork>=0&&li[j]<bin[n][k]{ bin[n][k+1]=bin[n][k] k-- } bin[n][k+1]=li[j] } o:=0 forp,q:=rangebin{ fort:=0;t<len(q);t++{ li[o]=bin[p][t] o++ } } }

10.基数排序

funcradix_sort(li[]int){ max_num:=li[0] fori:=0;i<len(li);i++{ ifmax_num<li[i]{ max_num=li[i] } } forj:=0;j<len(strconv.Itoa(max_num));j++{ bin:=make([][]int,10) fork:=0;k<len(li);k++{ n:=li[k]/int(math.Pow(10,float64(j)))%10 bin[n]=append(bin[n],li[k]) } m:=0 forp:=0;p<len(bin);p++{ forq:=0;q<len(bin[p]);q++{ li[m]=bin[p][q] m++ } } } }

11.用堆排解决top_k问题，思路：

a.先取前k个数建小根堆，这样就能保证堆顶元素是整个堆的最小值;

b.然后遍历列表的k到最后，如果值比堆顶大，就和堆顶交换，交换完后再对堆建小根堆，这样就能保证交换完后，堆顶元素仍然是整个堆的最小值；

c.一直遍历到列表的最后一个值，这一步做完之后，就保证了整个列表最大的前k个数已经放进了堆里；

d.按数的大到小出堆；

funcsift(li[]int,low,highint){ i:=low j:=2*i+1 tmp:=li[i] forj<=high{ ifj<high&&li[j]>li[j+1]{ j++ } iftmp>li[j]{ li[i]=li[j] i=j j=2*i+1 }else{ break } } li[i]=tmp } functop_k(li[]int,kint)[]int{ fori:=k/2-1;i>=0;i--{ sift(li,i,k-1) } forj:=k;j<len(li);j++{ ifli[0]<li[j]{ li[0],li[j]=li[j],li[0] sift(li,0,k-1) } } forn:=k-1;n>0;n--{ li[0],li[n]=li[n],li[0] sift(li,0,n-1) } returnli[:k] }

本文内容总结：

原文链接：https://www.cnblogs.com/Coufusion/p/9804655.html