归并排序实现mergesort和merge函数
时间: 2024-09-26 20:05:05 浏览: 15
归并排序是一种分治算法,它将待排序的序列递归地分成两半,对每一半分别进行排序,然后合并两个已排序的部分。整个过程可以分为两个主要步骤:
1. **分割(Divide)**:
- 将输入数组 `arr` 切分成两个相等长度的子数组,通常使用递归的方式,直到每个子数组只有一个元素,此时视为已经排序。
2. **合并(Merge)**:
- 定义一个名为 `merge` 的辅助函数,这个函数接受两个已排序的子数组 `left` 和 `right`,将它们合并成一个有序数组。
- 从两个数组的起始位置开始比较,选择较小的元素放入结果数组,并相应地移动原数组指针。
- 重复此过程,直到其中一个数组遍历完,然后将另一个数组剩余部分直接复制到结果数组中。
以下是 Python 中归并排序的一个简单实现,包含 `mergesort` 和 `merge` 函数:
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 分割数组
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 递归地对左右子数组进行排序
left = mergesort(left)
right = mergesort(right)
# 合并两个有序数组
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
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:])
merged.extend(right[j:])
return merged
# 示例
arr = [4, 2, 9, 6, 1, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)
```