python的归并排序法
时间: 2023-10-28 11:02:10 浏览: 50
归并排序是一种常用的排序算法,通过将待排序的序列分成若干个子序列,分别进行排序,然后再将排好序的子序列合并成一个有序的序列。下面是一个Python实现的归并排序算法的示例代码:
```python
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
left_array = merge_sort(left_array)
right_array = merge_sort(right_array)
return merge(left_array, right_array)
def merge(left_array, right_array):
result = []
i = 0
j = 0
while i < len(left_array) and j < len(right_array):
if left_array[i <= right_array[j]:
result.append(left_array[i])
i += 1
else:
result.append(right_array[j])
j += 1
result += left_array[i:]
result += right_array[j:]
return result
```
在这个示例中,`merge_sort`函数用于进行归并排序,首先判断数组的长度,如果长度小于等于1,则直接返回。然后找到数组的中间位置,将数组分为左右两个子数组。接着递归调用`merge_sort`函数对左右两个子数组进行排序。最后,调用`merge`函数将排好序的子数组合并为一个有序的数组。
`merge`函数用于合并两个有序的子数组。首先创建一个空的结果数组,然后使用两个指针`i`和`j`分别指向左子数组和右子数组的起始位置。接着比较左右子数组的元素大小,将较小的元素添加到结果数组中,并移动对应的指针。最后,将剩余的元素添加到结果数组中。
通过灵活运用归并排序算法,可以提高编写代码的效率。