python合并排序代码（python归并排序的实现原理）

原理分析

1
  
  
  
  
  
  
 、把一个序列从中间位置分成两个序列；

2  
  
  
  
  
  
 、把这两个子序列按第一步继续分成两部分；

3
 


 


 


 


 


 


 
、直到所有子序列的长度都是1
  
  
  
  
  
  
 ，也就是说  
  
  
  
  
  
 ，不能再有二分截止             。此时再两两合并成一个有序的序列
  
 
  
 
  
 
  
 
  
 
  
 
  。

实例

defmerge(arr,low,mid,high): #low和high为整个数组的第一个和最后一个位置索引
 


 


 


 


 


 


 
，mid为中间位置索引 #i和j为指针
 
 
 
 
 
 
，最初位置分别为两个有序序列的起始位置 #ltmp用来存放合并后的序列 i=low j=mid+1 ltmp=[] whilei<=midandj<=high:#只要左右两边都有数 ifarr[i]<arr[j]:#当左边的数小于右边的数 ltmp.append(arr[i])#将左边的数存入ltmp i+=1#左边的指针往右移一位 else:#当右边的数小于左边的数 ltmp.append(arr[j])#将右边的数存入ltmp j+=1#右边的指针往右移一位 #上面的while语句执行完后   
   
   
   
   
   
  ，左边或者右边没有数了 whilei<=mid:#当左边还有数的时候 ltmp.append(arr[i])#将左边剩下的数全部存入ltmp i+=1 whilej<=high:#当右边还有数的时候 ltmp.append(arr[j])#将右边剩下的数全部存入ltmp j+=1 arr[low:high+1]=ltmp#将排序后的数组写回原数组 defmerge_sort(arr,low,high):#low和high为整个数组的第一个和最后一个位置索引 iflow<high:#至少有两个元素 mid=(low+high)//2 merge_sort(arr,low,mid)#把左边递归分解 merge_sort(arr,mid+1,high)#把右边递归分解 merge(arr,low,mid,high)#做归并

以上就是python归并排序的实现原理
 

 

 

 

 

 

 
，希望对大家有所帮助












。更多Python学习指路：Python基础教程