用递归函数实现归并排序
时间: 2023-10-22 07:07:12 浏览: 54
好的,归并排序可以用递归函数实现,具体步骤如下:
1. 定义一个 merge() 函数,它接受两个已排好序的数组 left 和 right,并将它们合并成一个排好序的数组。
2. 定义一个 merge_sort() 函数,它接受一个未排序的数组 arr 和两个整数 start 和 end,表示要排序的子数组的起始和结束索引。
3. 在 merge_sort() 函数内部,如果子数组长度小于等于 1,则直接返回数组。
4. 否则,计算子数组的中间索引 mid,然后递归调用 merge_sort() 函数对左右两个子数组进行排序。
5. 最后,调用 merge() 函数将左右两个已排好序的子数组合并成一个排好序的数组,并返回该数组。
下面是代码实现:
```python
def merge(left, right):
result = []
i, j = 0, 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 += left[i:]
result += right[j:]
return result
def merge_sort(arr, start, end):
if start >= end:
return arr[start:end+1]
mid = (start + end) // 2
left = merge_sort(arr, start, mid)
right = merge_sort(arr, mid+1, end)
return merge(left, right)
arr = [5, 2, 8, 3, 1, 6]
print(merge_sort(arr, 0, len(arr)-1))
```
输出结果为:[1, 2, 3, 5, 6, 8]。