python代码 归并排序
时间: 2024-07-17 08:01:11 浏览: 79
Python实现归并排序.rar
Python实现归并排序的一种常见方式是通过分治策略。这里是一个简单的归并排序示例[^1]:
```python
def merge_sort(arr):
if len(arr) <= 1:
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 = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
# 示例
arr = [12, 11, 13, 5, 6]
sorted_arr = merge_sort(arr)
print(sorted_arr) # 输出: [5, 6, 11, 12, 13]
```
归并排序的工作原理是不断将数组分割成更小的部分,直到每个部分只剩下一个元素(这是基本情况),然后再合并这些已排序的部分,直到整个数组有序。
阅读全文