迭代归并排序的 Python 程序
pythonserver side programmingprogramming更新于 2024/1/22 23:52:00
在本文中，我们将了解下面给出的问题陈述的解决方案。
问题陈述− 给定一个数组，我们需要使用迭代归并排序的概念对其进行排序。
在这里，我们将最大元素放在末尾。重复此操作，直到数组排序完成。
现在让我们观察下面实现中的解决方案 −
示例
# 迭代方式
def mergeSort(a):
current_size = 1
# 遍历子数组
while current_size < len(a) - 1:
left = 0
# 正在排序的子数组
while left < len(a)-1:
# 计算中间值
mid = left + current_size - 1
# current_size
right = ((2 * current_size + left - 1, len(a) - 1)[2 * current_size + left - 1 > len(a)-1])
# 合并
merge(a, left, mid, right)
left = left + current_size*2
# 增加子数组大小
current_size = 2 * current_size
# Merge
def merge(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1] i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1
else:
a[k] = L[i]
i += 1
k += 1
while i < n1:
a[k] = L[i]
i += 1
k += 1
while j < n2:
a[k] = R[j]
j += 1
k += 1
# 驱动代码
a = [2,5,3,8,6,5,4,7]
mergeSort(a)
print("Sorted array is:")
for i in range(len(a)):
print (a[i],end=" ")
输出
Sorted array is 2 3 4 5 5 6 7 8
所有变量均在本地范围内声明，其引用如上图所示。
结论
在本文中，我们了解了如何编写用于迭代归并排序的 Python 程序
