【重温篇】八大排序——归并排序

**重温篇**: 八大排序——归并排序在计算机科学中，排序算法是非常重要的概念。它能够帮助我们对一组数据进行有序排列，从而更好地分析和处理这些数据。在本文中，我们将重点介绍一种常见且高效的排序算法——归并排序。

**什么是归并排序**

归并排序是一种分治法（Divide and Conquer）的排序算法。它通过递归地将一组数据分成两个子集，然后分别对这两个子集进行排序，最终合并两个有序的子集来得到最终结果。

**归并排序的步骤**

1. **分割**: 将一组数据分成两个子集。
2. **递归**: 对每个子集重复上述过程，直到子集中的元素只有一个。
3. **合并**: 将两个有序的子集合并起来。

**归并排序的实现**

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

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

 # 递归对每个子集进行排序 left_half = merge_sort(left_half)
 right_half = merge_sort(right_half)

 # 合并两个有序的子集 return merge(left_half, right_half)


def merge(left, right):
 merged = []
 left_index =0 right_index =0 while left_index < len(left) and right_index < len(right):
 if left[left_index] <= right[right_index]:
 merged.append(left[left_index])
 left_index +=1 else:
 merged.append(right[right_index])
 right_index +=1 # 如果有剩余的元素，则追加到合并结果中 merged.extend(left[left_index:])
 merged.extend(right[right_index:])

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