C++/GoLang如何实现自底向上的归并排序

2023-07-17 15:40:04 77

template voidmergeSortButton2Top(Tarr[],intn){ for(intsize=1;size<=n;size+=size){ for(inti=0;i+sizen了，越界了，就取n-1 } } template void__merge(Tarr[],intleft,intmid,intright){//将arr[left,mid]和arr[mid+1,right]两部分进行归并 T*tmp=newT[right-left+1]; for(inti=left;i<=right;i++) tmp[i-left]=arr[i];//先把arr（需要合并的左右片段）复制给tmp inti=left,j=mid+1;//i做为左半部分的指针j作为右半部分的指针 for(intk=left;k<=right;k++){ if(i>mid){//左半部分已经合入完了，将右半部分剩下的全部合入 arr[k]=tmp[j-left]; j++; } elseif(j>right){//右半部分已经合入完了，将左半部分剩下的全部合入 arr[k]=tmp[i-left]; i++; } elseif(tmp[i-left]

GoLang实现:

funcmergeSortButton2Top(arr[]int){
varlenthint=len(arr)
forsize:=1;size<=lenth;size+=size{
fori:=0;i+sizen了，越界了，就取n-1
}
}
}

funcmerge(arr[]int,left,mid,rightint){
//将要合并的部分做个拷贝
vartmp[]int=make([]int,right-left+1)
fori,j:=left,0;i<=right;i++{
tmp[j]=arr[i]
j++
}
//i做为左半部分的指针j作为右半部分的指针
vari,jint=left,mid+1
fork:=left;k<=right;k++{
ifi>mid{//左半部分已经合入完了，将右半部分剩下的全部合入
arr[k]=tmp[j-left]
j++
}elseifj>right{//右半部分已经合入完了，将左半部分剩下的全部合入
arr[k]=tmp[i-left]
i++
}elseiftmp[i-left]>tmp[j-left]{
arr[k]=tmp[j-left]
j++
}else{
arr[k]=tmp[i-left]
i++
}
}
}

用golang对两种归并排序进行计时，观察性能：

funccreateRandomArray(countint)[]int{
rand.Seed(time.Now().UnixNano())
vararr[]int=make([]int,0)
fori:=0;i
因为自底向上少了二分那个步骤，性能要优于自顶向下的归并排序
总结
到此这篇关于C++/GoLang如何实现自底向上的归并排序的文章就介绍到这了,更多相关C++/GoLang自底向上的归并排序内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++/GoLang如何实现自底向上的归并排序

热门推荐

随机推荐