Python 3 教程
Python 歸并排序
Python3 實(shí)例歸并排序（英語：Merge sort，或mergesort），是創(chuàng)建在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
分治法:
- 分割：遞歸地把當(dāng)前序列平均分割成兩半。
- 集成：在保持元素順序的同時(shí)將上一步得到的子序列集成到一起（歸并）。
實(shí)例
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
# 創(chuàng)建臨時(shí)數(shù)組
L = [0] * (n1)
R = [0] * (n2)
# 拷貝數(shù)據(jù)到臨時(shí)數(shù)組 arrays L[] 和 R[]
for i in range(0 , n1):
L[i] = arr[l + i]
for j in range(0 , n2):
R[j] = arr[m + 1 + j]
# 歸并臨時(shí)數(shù)組到 arr[l..r]
i = 0 # 初始化第一個(gè)子數(shù)組的索引
j = 0 # 初始化第二個(gè)子數(shù)組的索引
k = l # 初始?xì)w并子數(shù)組的索引
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
def mergeSort(arr,l,r):
if l < r:
m = int((l+(r-1))/2)
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("給定的數(shù)組")
for i in range(n):
print ("%d" %arr[i]),
mergeSort(arr,0,n-1)
print ("nn排序后的數(shù)組")
for i in range(n):
print ("%d" %arr[i]),
執(zhí)行以上代碼輸出結(jié)果為：
給定的數(shù)組 12 11 13 5 6 7 排序后的數(shù)組 5 6 7 11 12 13其他擴(kuò)展