python归并排序的代码
时间: 2024-08-15 20:10:01 浏览: 28
Python中的归并排序是一种分治算法,它将数组分为两个半部分,对每个部分递归地排序,然后合并这两个已排序的部分。以下是归并排序的基本Python实现:
```python
def merge_sort(arr):
# 如果数组长度小于2,就认为已经排好序,返回数组本身
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 = []
left_index, right_index = 0, 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 = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
sorted_arr = merge_sort(arr)
print(sorted_arr)