归并排序的基本思想¶
归并排序是一种基于分治法（Divide and Conquer）的高效排序算法。它的核心思路可以概括为三个步骤：分解（Divide）、递归排序（Conquer） 和 合并（Merge）。
- 分解：将待排序的数组从中间分成左右两部分，直到每个子数组只包含一个元素（此时子数组本身就是有序的）。
- 递归排序：对左右两个子数组分别递归执行归并排序，直到所有子数组都有序。
- 合并：将两个已排序的子数组合并成一个更大的有序数组，最终得到整个数组的排序结果。
简单来说，归并排序就是先把大问题拆分成小问题，解决小问题后再把结果合并起来。
分解过程详解¶
假设我们有一个数组 [3, 1, 4, 2]，归并排序的分解过程如下：
- 第一次分解：数组长度为4，中间位置是
4//2=2，所以分成左右两部分：left = [3, 1]和right = [4, 2]。 - 递归分解左子数组
[3, 1]：中间位置是2//2=1，分成left_left = [3]和left_right = [1]（每个子数组长度为1，无需再分解）。 - 递归分解右子数组
[4, 2]：中间位置是2//2=1，分成right_left = [4]和right_right = [2]（每个子数组长度为1，无需再分解）。
递归排序与合并¶
当分解到子数组长度为1时，子数组已经有序（单个元素本身就是有序的）。此时需要执行合并操作，将两个有序子数组合并成一个更大的有序数组。
以分解后的子数组为例：
- 左子数组合并：[3] 和 [1] 合并成 [1, 3]。
- 右子数组合并：[4] 和 [2] 合并成 [2, 4]。
- 最终合并：[1, 3] 和 [2, 4] 合并成 [1, 2, 3, 4]。
Python代码实现¶
下面是归并排序的Python实现，分为合并函数和递归排序函数两部分：
1. 合并函数 merge(left, right)¶
功能：合并两个已排序的子数组，返回一个新的有序数组。
def merge(left, right):
merged = [] # 存储合并后的结果
i = j = 0 # 两个子数组的指针（索引）
# 比较两个子数组的元素，按顺序加入merged
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# 将剩余未比较的元素直接加入（可能其中一个子数组已遍历完）
merged.extend(left[i:]) # 添加left中剩余元素
merged.extend(right[j:]) # 添加right中剩余元素
return merged
2. 递归排序函数 merge_sort(arr)¶
功能：递归分解数组，调用合并函数得到排序结果。
def merge_sort(arr):
# 基本情况：数组长度为1或0时，本身就是有序的
if len(arr) <= 1:
return arr
# 分解数组：分成左右两部分
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 递归排序左半部分
right = merge_sort(arr[mid:]) # 递归排序右半部分
# 合并两个已排序的子数组
return merge(left, right)
测试代码¶
if __name__ == "__main__":
test_array = [3, 1, 4, 2, 5]
sorted_array = merge_sort(test_array)
print("原始数组:", test_array)
print("排序后数组:", sorted_array)
输出结果：
原始数组: [3, 1, 4, 2, 5]
排序后数组: [1, 2, 3, 4, 5]
归并排序的特点¶
- 时间复杂度：无论输入数组如何，归并排序的时间复杂度始终为 O(n log n)（分解和合并的总操作次数为O(n log n)）。
- 空间复杂度：需要额外的数组存储合并结果，空间复杂度为 O(n)。
- 稳定性：归并排序是稳定的排序算法（相等元素的相对顺序保持不变）。
归并排序的核心是“分而治之”和“合并有序数组”，通过递归分解和合并，最终实现整个数组的排序。虽然代码看起来比冒泡排序等简单排序算法复杂，但理解其思路后，会发现它非常直观且高效。