如何用Python编写归并排序算法？

本文共计863个文字，预计阅读时间需要4分钟。

归并排序是一种经典的排序算法，其核心思想是将待排序数组分割成若干个已排序的子数组，对这些子数组进行排序，最后将排好序的子数组合并成一个有序数组。归并排序效率较高。

归并排序是一种经典的排序算法，其核心思想是将待排序数组分成若干个子数组，对这些子数组进行排序，最后再将排好序的子数组合并成一个有序数组。归并排序是一种效率较高的排序算法，其时间复杂度为O(nlogn)。

在本文中，我们将讲解如何用Python实现归并排序。

1. 实现归并排序的思路

归并排序的实现思路包括两个部分，分别是分治和合并。具体实现步骤如下：

1）将待排序数组不断一分为二，递归地对左右两部分进行排序；

2）将排好序的左右两部分合并成一个有序数组。

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，则直接返回该数组。