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