Python 归并排序

最后更新于：2022-03-27 02:37:29

Python 归并排序

Python 归并排序 Python3 实例

归并排序（英语：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 ("\n\n排序后的数组")
for i in range(n):
print ("%d" %arr[i]),

执行以上代码输出结果为：

给定的数组
12
11
13
5
6
7


排序后的数组
5
6
7
11
12
13

Python 归并排序 Python3 实例