归并排序Python
时间: 2024-05-08 13:13:38 浏览: 15
归并排序是一种分治算法,它将原始数组分成较小的数组,直到每个小部分只有一个元素,然后通过递归地将小数组合并成更大的数组,直到最终排序完成。
具体来说,归并排序的步骤如下:
1. 将原始数组拆分成两个较小的数组,直到每个小数组只有一个元素。
2. 递归地将每个小数组进行排序。
3. 合并两个有序的小数组成一个大数组。
在Python中,归并排序的实现如下:
```
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_arr = arr[:mid]
right_arr = arr[mid:]
merge_sort(left_arr)
merge_sort(right_arr)
i = j = k = 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
arr[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1
```