（笔记）归并排序

**归并排序笔记**

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

###1. 算法描述归并排序的基本思想是：

* 将一个长度为 n 的数组分成两个长度为 n/2 的子数组。
* 递归地对这两个子数组进行排序。
* 合并两个有序子数组得到最终结果。

###2. 算法步骤1. **分解**: 将一个长度为 n 的数组分成两个长度为 n/2 的子数组。
2. **递归排序**: 递归地对这两个子数组进行排序。
3. **合并**: 合并两个有序子数组得到最终结果。

###3. 归并排序的实现####3.1 归并函数

def merge(left, right):
 """
 合并两个有序列表 Args:
 left (list): 左边的列表 right (list): 右边的列表 Returns:
 list: 合并后的列表 """
 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

def merge_sort(arr):
 """
 归并排序 Args:
 arr (list): 需要排序的列表 Returns:
 list: 排序后的列表 """
 # 如果长度为1或0，则直接返回 if len(arr) <=1:
 return arr # 将数组分成两个子数组 mid = len(arr) //2 left = arr[:mid]
 right = arr[mid:]
 # 递归地对这两个子数组进行排序 left = merge_sort(left)
 right = merge_sort(right)
 # 合并两个有序子数组得到最终结果 return merge(left, right)

arr = [64,34,25,12,22,11,90]
print("原始列表:", arr)
sorted_arr = merge_sort(arr)
print("排序后的列表:", sorted_arr)

原始列表: [64,34,25,12,22,11,90]
排序后的列表: [11,12,22,25,34,64,90]