golang/python实现归并排序实例代码
归并排序
思路：将数组不断二分，然后合并为有序数组
C++实现:
voidmergeSort(Tarr[],intleft,intright){//对arr[left,right]的范围进行排序
if(left>=right)
return;
intmid=(left+right)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);//合并两部分
}
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实现:
funcmergeSort(arr[]int,left,rightint){
ifleft>=right{
return
}
mid:=left+(right-left)/2
mergeSort(arr,left,mid)//递归调用，分别对左右部分进行归并排序
mergeSort(arr,mid+1,right)
merge(arr,left,mid,right)//将左右部分进行合并
}
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++
}
}
}
python实现:
python的实现方法和上面不一样，上面两种方法都是在原始数组上直接进行修改的
defmergeSort(arr):
iflen(arr)<=1:
returnarr
mid=len(arr)//2
left=mergeSort(arr[:mid])#分别对左右部分排序
right=mergeSort(arr[mid:])
returnmerge(left,right)#合并左右部分为有序数组
defmerge(left,right):
result=[]
num_left,num_right=left.pop(0),right.pop(0)#分别取出左右部分的第0个元素
whileTrue:
ifnum_left
总结
到此这篇关于golang/python实现归并排序的文章就介绍到这了,更多相关golangpython归并排序内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。