VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > python入门教程 >
  • Python 归并排序法

归并排序法:是采用分治法的一个非常典型的应用。

分治法:

分割:递归地把当前序列平均分割成两半。

集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。

 

#归并排序法

#1、合并的过程函数

# left 开始索引下标;m数组中间值下标;right结束索引下标

def merge(arr,left,m,right):
  n1=m-left+1 #前子数组的长度
  n2=right-m #后子数组的长度

  #创建临时数组
  L=[0]*n1
  R=[0]*n2

  #拷贝数据到临时数组
  for i in range(0,n1): #把前子数组的元素拷贝到左边的临时数组
    L[i]=arr[left+i]

  for j in range(0,n2): #把后子数组的元素拷贝到右边的临时数组
    R[j]=arr[m+1+j]

  #归并临时数组到 arr[1..r]

  #把左右临时数组的元素,按大小合并到原数组中

  i=0  #初始化第一个子数组的索引
  j=0  #初始化第二个子数组的索引
  k=left #初始归并子数组的索引

  while i < n1 and j<n2:
    if L[i]<=R[j]:  【<=:是按有小到大的顺序;>=:是按由大到小的顺序
      arr[k]=L[i]
      i+=1
    else:
      arr[k]=R[j]
      j+=1

  k +=1

  #拷贝 L[] 剩下的保留元素

  #如果右边的数字元素都并入完了,左边数组还有元素,则不需要再进行比较,集中并入
  while i<n1:
    arr[k]=L[i]
    i+=1
    k+=1

  #拷贝 R[]剩下 的保留元素

  #如果左边的数字元素都并入完了,右边数组还有元素,则不需要再进行比较,集中并入
  while j<n2:
    arr[k]=R[j]
    j+=1
    k+=1

#2、分 的过程

#先分:一直分到单个元素后,从单个元素再合并的操作

def mergeSort(arr,left,right):

  if left >= right:
    return

  m=int((left+right)/2)

  mergeSort(arr,left,m) #递归对数列的前半部分进行分开
  mergeSort(arr,m+1,right) #递归对数列的后半部分进行分开
  merge(arr,left,m,right) #从分开后的单个元素开始进行合并

 

#测试
arr=[8,4,7,5,3,1,6,2]
n=len(arr)

mergeSort(arr,0,n-1)
print("排序后的数值")
for i in range(n):
print("%d" %arr[i])



来源:https://www.cnblogs.com/xiangers/p/15458333.html


相关教程