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.uj5u.com/houduan/336113.html

標籤：Python