Python 中的合并排序
Vaibhhav Khetarpal
2023年1月30日
2022年5月17日
合并排序是一种流行的排序算法，用于对任何给定数据结构的元素进行排序。本教程讨论了归并排序算法以及如何在 Python 中实现它。
合并排序是分治法的一个主要例子，用于对大型数据集进行排序。该算法首先将给定的数据结构分成两部分，然后在两半上重复相同的过程。最后，它将两半重新组合在一起以有效地获得排序值。因此，我们称其为分而治之方法的主要例子。
这个算法最好的部分是它在所有三种可能的情况下（平均情况、最佳情况和最坏情况）都具有一致的时间复杂度 O(nlogn)。由于这个事实，它通常被认为是有效的，并且是大型数据集的首选。
我们现在将看到如何使用 Python 编程语言实现归并排序算法。
在 Python 中使用递归实现归并排序
归并排序是在 Python 中借助递归函数简单实现的。
以下代码使用递归在 Python 中实现归并排序。
def m(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while (len(result) < len(left) + len(right)):
if left[i] < right[j]:
result.append(left[i])
i+= 1
else:
result.append(right[j])
j+= 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def msort(list):
if len(list) < 2:
return list
middle = int(len(list)/2)
left = msort(list[:middle])
right = msort(list[middle:])
return m(left, right)
lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst);
print("\n")
print("Sorted List:")
print(msort(lst))
上面的代码提供了以下输出：
Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]
代码说明：
- 只要没有获得两个相邻的值，在每次递归调用中，给定的列表都会分成两半，
左和右。 - 创建并使用
m()函数来合并最初在第一步中划分的两半。 msort()函数执行程序中给定列表的大部分划分和排序部分。
在 Python 中使用迭代合并排序
迭代归并排序算法与一般的递归方法略有不同，前者使用自下而上的方法，而后者使用自上而下的方法。但是，两种方法的时间复杂度和最终答案完全相同。
此外，递归归并排序方法使用显式辅助堆栈，而在迭代归并排序算法实现中则不需要它。
以下代码使用迭代归并排序算法在 Python 中实现归并排序。
def msort(a):
width = 1
n = len(a)
while (width < n):
l=0;
while (l < n):
r = min(l+(width*2-1), n-1)
m = (l+r)//2
if (width>n//2):
m = r-(n%width)
mer(a, l, m, r)
l += width*2
width *= 2
return a
def mer(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 = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)
上面的代码提供了以下输出：
Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]
归并排序的缺点
尽管归并排序真的很流行并且被认为是高效的，但它在各种情况下都有一些缺点，下面会提到。
- 在处理较小的数据结构集时，它可能比其他可用的排序算法相对慢。
- 实现此算法需要额外的内存空间。
- 该算法将始终贯穿整个过程，即使给定的数据结构已经排序。
Author: Vaibhhav Khetarpal
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn