python二分归并排序代码
时间: 2023-10-29 19:57:37 浏览: 69
下面是一个用Python实现的二分归并排序的代码:
```python
def merge_sort(alist):
if len(alist) <= 1:
return alist
# 二分分解
num = len(alist) // 2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# 合并
return merge(left, right)
def merge(left, right):
'''合并操作,将两个有序数组left[]和right[]合并成一个大的有序数组'''
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result.extend(left[l:])
result.extend(right[r:])
return result
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_alist = merge_sort(alist)
print(sorted_alist)
```
这段代码通过递归地将数组分解为最小单位后再合并两个有序数组来实现归并排序。首先,代码中的`merge_sort`函数将输入的数组递归地分解为左右两个子数组,然后调用`merge`函数将这两个子数组按顺序合并成一个有序数组。`merge`函数中,通过比较两个数组的第一个元素,选择较小的元素放入结果数组中,并更新相应的指针。当其中一个数组为空时,将另一个数组的剩余部分直接加入结果数组。最后,`merge_sort`函数返回的就是最终的有序数组。
以上就是用Python实现的二分归并排序的代码。