python 归并排序
归并排序（英语：merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（divide and conquer）的一个非常典型的应用。
分治法:
- 分割：递归地把当前序列平均分割成两半。
- 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
实例
def merge(arr, l, m, r):
n1 = m - l + 1 n2 = r- m
# 创建临时数组 l = [0] * (n1) r = [0] * (n2)
# 拷贝数据到临时数组 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]
# 归并临时数组到 arr[l..r] i = 0 # 初始化第一个子数组的索引 j = 0 # 初始化第二个子数组的索引 k = l # 初始归并子数组的索引
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 ("给定的数组") for i in range(n):
print ("%d" %arr[i]),
mergesort(arr,0,n-1) print ("nn排序后的数组") for i in range(n):
print ("%d" %arr[i]),
执行以上代码输出结果为：
给定的数组 12 11 13 5 6 7 排序后的数组 5 6 7 11 12 13
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！