Python 实现的 DSA 归并排序
归并排序
归并排序（Merge Sort）算法是一种分治算法，它先将数组拆分成更小的数组，然后以正确的方式重新组合数组，从而实现排序。
{{ msgDone }}
分解：该算法首先将数组不断拆分成更小的部分，直到子数组仅包含一个元素。
合并：该算法通过将最小值放在前面，将数组的小部分重新组合在一起，从而得到一个已排序的数组。
归并排序通过递归的方式对数组进行拆分和重组。
在上面的动画中，每次条形图下移都代表一次递归调用，将数组拆分成更小的部分。当条形图上移时，表示两个子数组合并完成。
归并排序算法的描述如下：
工作原理：
- 将未排序的数组分成两个子数组，每个子数组的大小为原数组的一半。
- 只要当前数组部分包含多个元素，就继续拆分子数组。
- 通过始终将最小值放在前面来合并两个子数组。
- 持续合并，直到没有子数组剩下。
请查看下面的图示，从不同的角度了解归并排序的工作原理。如图所示，数组被拆分成越来越小的部分，直到重新合并在一起。在合并过程中，会对每个子数组的值进行比较，以确保最小值排在最前面。
手动运行示例
在实际使用 Python 程序实现归并排序之前，让我们先手动进行排序，以便更好地理解归并排序的工作原理。
第 1 步：我们从一个未排序的数组开始，我们知道它会一直拆分，直到子数组仅包含一个元素。归并排序函数会调用自身两次，每次处理数组的一半。这意味着第一个子数组将首先拆分成最小的部分。
[ 12, 8, 9, 3, 11, 5, 4] [ 12, 8, 9] [ 3, 11, 5, 4] [ 12] [ 8, 9] [ 3, 11, 5, 4] [ 12] [ 8] [ 9] [ 3, 11, 5, 4]
第 2 步：第一个子数组的拆分已完成，现在是时候进行合并了。8 和 9 是要合并的前两个元素。8 是最小值，因此在第一个合并的子数组中，8 排在 9 前面。
[ 12] [ 8, 9] [ 3, 11, 5, 4]
第 3 步：接下来要合并的子数组是 [ 12] 和 [ 8, 9]。从开头开始比较两个数组中的值。8 小于 12，因此 8 排在前面，9 也小于 12。
[ 8, 9, 12] [ 3, 11, 5, 4]
第 4 步：现在递归拆分第二个大的子数组。
[ 8, 9, 12] [ 3, 11, 5, 4] [ 8, 9, 12] [ 3, 11] [ 5, 4] [ 8, 9, 12] [ 3] [ 11] [ 5, 4]
第 5 步：3 和 11 按照所示顺序合并在一起，因为 3 小于 11。
[ 8, 9, 12] [ 3, 11] [ 5, 4]
第 6 步：包含值 5 和 4 的子数组被拆分，然后合并，使 4 排在 5 前面。
[ 8, 9, 12] [ 3, 11] [ 5] [ 4] [ 8, 9, 12] [ 3, 11] [ 4, 5]
第 7 步：合并右侧的两个子数组。通过比较创建新合并数组中的元素：
- 3 小于 4
- 4 小于 11
- 5 小于 11
- 11 是最后剩下的值
[ 8, 9, 12] [ 3, 4, 5, 11]
第 8 步：合并最后剩下的两个子数组。让我们更详细地了解如何进行比较，以创建新的合并数组并完成排序：
3 小于 8：
之前: [ 8, 9, 12] [ 3, 4, 5, 11] 之后: [ 3, 8, 9, 12] [ 4, 5, 11]
第 9 步：4 小于 8：
之前: [ 3, 8, 9, 12] [ 4, 5, 11] 之后: [ 3, 4, 8, 9, 12] [ 5, 11]
第 10 步：5 小于 8：
之前: [ 3, 4, 8, 9, 12] [ 5, 11] 之后: [ 3, 4, 5, 8, 9, 12] [ 11]
第 11 步：8 和 9 小于 11：
之前: [ 3, 4, 5, 8, 9, 12] [ 11] 之后: [ 3, 4, 5, 8, 9, 12] [ 11]
第 12 步：11 小于 12：
之前: [ 3, 4, 5, 8, 9, 12] [ 11] 之后: [ 3, 4, 5, 8, 9, 11, 12]
排序完成！
运行下面的模拟程序，查看上述步骤的动画演示：
在 Python 中实现归并排序
要实现归并排序算法，我们需要：
- 包含待排序值的数组。
- 一个函数，该函数接受一个数组，将其拆分成两部分，并分别对每一部分调用自身，以便不断递归拆分数组，直到子数组仅包含一个值。
- 另一个函数，该函数以排序的方式重新合并子数组。
生成的代码如下所示：
实例
在 Python 中实现归并排序算法：
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]
sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)
return merge(sortedLeft, sortedRight)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print("Sorted array:", mysortedlist)
在第 6 行，arr[:mid] 获取数组中直到但不包括索引 'mid' 处的值的所有值。
在第 7 行，arr[mid:] 获取数组中从索引 'mid' 处的值开始的所有值以及接下来的所有值。
在第 26-27 行，完成了合并的第一部分。此时，比较了两个子数组的值，并且左子数组或右子数组为空，因此结果数组可以直接用左子数组或右子数组中剩余的值填充。这些行可以互换，结果将保持不变。
非递归归并排序
由于归并排序是一种分治算法，因此递归是实现该算法最直观的代码。递归实现的归并排序可能也更容易理解，并且通常使用的代码行数更少。
但是，归并排序也可以在不使用递归的情况下实现，即没有函数调用自身的情况。
请查看下面不使用递归的归并排序实现：
实例
不使用递归的归并排序：
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def mergeSort(arr):
step = 1 # 从长度为 1 的子数组开始
length = len(arr)
while step < length:
for i in range(0, length, 2 * step):
left = arr[i:i + step]
right = arr[i + step:i + 2 * step]
merged = merge(left, right)
# 将合并后的数组放回原数组
for j, val in enumerate(merged):
arr[i + j] = val
step *= 2 # 将子数组长度加倍，以便进行下一次迭代
return arr
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print(mysortedlist)
您可能会注意到，在上述两个归并排序实现中，merge 函数完全相同，但在上面的实现中，mergeSort 函数中的 while 循环用于替代递归。while 循环在原地对数组进行拆分和合并，这使得代码稍微难以理解。
简而言之，mergeSort 函数中的 while 循环使用短步长，利用 merge 函数对初始数组的微小部分（子数组）进行排序。然后，增加步长以合并和排序数组的较大部分，直到整个数组排序完成。
归并排序的时间复杂度
归并排序的时间复杂度为：\( O( n \cdot \log n ) \)。
对于不同类型的数组，时间复杂度几乎相同。无论数组是否已经排序或完全打乱，该算法都需要拆分数组并重新合并。
下图显示了归并排序的时间复杂度。
无论数组是否已经排序，归并排序的性能几乎都相同，因为无论何种情况，都需要拆分数组并使用比较进行合并。