归并排序是一种经典的排序算法，其核心思想是将待排序数组分成若干个子数组，对这些子数组进行排序，最后再将排好序的子数组合并成一个有序数组。归并排序是一种效率较高的排序算法，其时间复杂度为o(nlogn)。
在本文中，我们将讲解如何用Python实现归并排序。
归并排序的实现思路包括两个部分，分别是分治和合并。具体实现步骤如下：
1）将待排序数组不断一分为二，递归地对左右两部分进行排序；
2）将排好序的左右两部分合并成一个有序数组。
立即学习“Python免费学习笔记（深入）”；
分治是归并排序的核心思想，我们需要先实现分治的部分。
代码如下：
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_arr = merge_sort(arr[:mid])
right_arr = merge_sort(arr[mid:])
return merge(left_arr, right_arr)在这个函数中，我们首先判断如果数组长度小于等于1，则直接返回该数组。否则，我们需要将该数组一分为二，分别对左右两部分进行递归排序，最后再将排好序的左右两部分合并起来。
2.1 实现合并
在实现分治的基础上，我们需要实现合并的部分。
代码如下：
def merge(left_arr, right_arr):
i, j = 0, 0
result = []
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
result.append(left_arr[i])
i += 1
else:
result.append(right_arr[j])
j += 1
result += left_arr[i:]
result += right_arr[j:]
return result在这个函数中，我们先初始化指针i和j，分别指向左右两部分要比较的元素。接着我们不断比较左右两部分元素，将较小的元素添加到结果列表中，并将该指针右移。最后，我们还要将剩下的所有元素添加到结果列表中，以便最终得到排好序的数组。
将分治和合并部分组合起来，得到完整代码如下：
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_arr = merge_sort(arr[:mid])
right_arr = merge_sort(arr[mid:])
return merge(left_arr, right_arr)
def merge(left_arr, right_arr):
i, j = 0, 0
result = []
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
result.append(left_arr[i])
i += 1
else:
result.append(right_arr[j])
j += 1
result += left_arr[i:]
result += right_arr[j:]
return result为了验证我们的归并排序代码是否正确，我们需要进行测试。
代码如下：
arr = [5, 3, 8, 6, 4, 7, 2, 1] print(merge_sort(arr))
输出结果为：
[1, 2, 3, 4, 5, 6, 7, 8]
测试结果表明，我们的归并排序代码是正确的。
以上就是如何用Python实现归并排序的详细内容，更多请关注php中文网其它相关文章！
python怎么学习？python怎么入门？python在哪学？python怎么学才快？不用担心，这里为大家提供了python速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
604
收藏
