def merge_sort(nums): if len(nums) <= 1: return nums mid = len(nums) // 2 left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) return merge(left, right)
时间: 2024-03-23 20:42:57 浏览: 64
这是一个归并排序的 Python 实现,它将传入的列表按照从小到大的顺序进行排序。该算法的基本思路是将列表分成两个部分,递归地对每个部分进行排序,然后将排序后的两个部分合并成一个有序的列表。这个过程一直递归下去,直到每个部分只剩下一个元素,然后再将它们合并成一个有序的列表。
在这个实现中,merge_sort 函数接收一个列表作为参数,如果列表长度小于等于1,直接返回该列表。否则,将列表分成两个部分,分别对这两个部分调用 merge_sort 函数,得到排好序的两个部分 left 和 right,然后调用 merge 函数将它们合并成一个有序的列表并返回。merge 函数的实现可以参考下面的代码:
```
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
```
这个函数接收两个有序列表 left 和 right,返回将它们合并成一个有序列表的结果。具体实现是维护两个指针 i 和 j,分别指向 left 和 right 的第一个元素,比较它们的大小,将较小的元素加入到结果列表中,然后移动指针,直到其中一个指针到达列表末尾。最后将剩余的部分添加到结果列表中即可。
阅读全文