归并排序
归并排序是一种基于分治思想的排序算法，它将待排序的列表分割成较小的子列表，然后递归地对子列表进行排序，最后将排好序的子列表合并以得到完整的有序列表。
算法步骤：
- 将待排序列表分割成长度相等（或相差最多1）的两个子列表。
- 递归地对两个子列表进行归并排序，直到子列表长度为1。
- 将排好序的子列表合并，得到一个新的有序列表。
- 重复步骤3，直到所有子列表都被合并成一个有序列表。
示例
下面是用Python编写的归并排序算法示例：
代码语言：javascript复制def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_idx = 0
right_idx = 0
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] <= right[right_idx]:
merged.append(left[left_idx])
left_idx = 1
else:
merged.append(right[right_idx])
right_idx = 1
while left_idx < len(left):
merged.append(left[left_idx])
left_idx = 1
while right_idx < len(right):
merged.append(right[right_idx])
right_idx = 1
return merged
# 测试示例
nums = [64, 25, 12, 22, 11]
sorted_nums = merge_sort(nums)
print("排序后的数组:", sorted_nums)
在这个示例中，我们定义了两个函数：merge_sort和merge。函数merge_sort接受一个列表arr作为输入，并通过递归地对子列表进行归并排序来对其进行排序。函数merge用于合并两个有序子列表。
可视化
现在让我们通过可视化展示归并排序算法的执行过程，以加深对算法的理解。
代码语言：javascript复制以下是归并排序的可视化示例：
原始数组: [64, 25, 12, 22, 11]
拆分过程:
[64, 25, 12, 22, 11] -> [64, 25] [12, 22, 11] -> [64] [25] [12] [22, 11] -> [64] [25] [12] [22] [11]
合并过程:
[64] [25] -> [25, 64]
[12] [22] [11] -> [11, 12, 22]
[25, 64] [11, 12, 22] -> [11, 12, 22, 25, 64]
排序后的数组: [11, 12, 22, 25, 64]
通过这个可视化示例，你可以看到归并排序算法是如何将列表分割成较小的子列表，并通过合并排好序的子列表来逐步构建有序列表的。
下集预告
这就是第七天的教学内容，关于归并排序算法的原理、示例代码以及可视化展示。如果你有任何问题，请随时留言。
