[数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

**数据结构 -- 手撕排序算法第七篇**

**递归实现归并排序**

在前六篇文章中，我们已经学习了各种排序算法，如选择排序、插入排序、冒泡排序等。今天我们要讲的就是一种非常重要的排序算法——归并排序。

归并排序是一种分治法，通过递归地将数组分成两个子数组，然后对这两个子数组进行排序，最终合并两个有序的子数组得到最终结果。

**归并排序的实现**

下面是递归实现归并排序的代码：

def merge_sort(arr):
 # 如果数组长度小于2，直接返回，因为已经有序 if len(arr) < 2:
 return arr # 找到中间索引，将数组分成两个子数组 mid = len(arr) //2 left = arr[:mid]
 right = arr[mid:]

 # 递归地对两个子数组进行排序 left = merge_sort(left)
 right = merge_sort(right)

 # 合并两个有序的子数组得到最终结果 return merge(left, right)


def merge(left, right):
 result = []
 while len(left) >0 and len(right) >0:
 if left[0] <= right[0]:
 result.append(left.pop(0))
 else:
 result.append(right.pop(0))

 # 如果有剩余的元素，直接追加到结果中 result.extend(left)
 result.extend(right)

 return result# 测试代码arr = [64,34,25,12,22,11,90]
print("原始数组：", arr)
sorted_arr = merge_sort(arr)
print("排序后数组：", sorted_arr)

**如何理解归并排序的实现**

在上面的代码中，我们定义了两个函数：`merge_sort` 和 `merge`。

* `merge_sort` 函数负责递归地将数组分成两个子数组，然后对这两个子数组进行排序，最终合并两个有序的子数组得到最终结果。
* `merge` 函数负责合并两个有序的子数组得到最终结果。

在 `merge_sort` 函数中，我们首先检查数组长度是否小于2，如果是，则直接返回，因为已经有序。然后我们找到中间索引，将数组分成两个子数组，分别对这两个子数组进行排序，最终合并两个有序的子数组得到最终结果。

在 `merge` 函数中，我们首先创建一个空列表 `result` 来存储最终结果。在循环体内，我们不断比较两个子数组的第一个元素，如果左边的元素小于右边的元素，则将左边的元素追加到 `result` 中，否则将右边的元素追加到 `result` 中。最后，我们检查有剩余的元素是否存在，如果有，则直接追加到 `result` 中。

**总结**

归并排序是一种非常重要的排序算法，它通过递归地将数组分成两个子数组，然后对这两个子数组进行排序，最终合并两个有序的子数组得到最终结果。通过上面的代码示例和注释，我们可以更好地理解归并排序的实现原理。

**参考**

* [Wikipedia - Merge sort]( />* [GeeksforGeeks - Merge Sort](