Python 算法教程（5）：归并排序详解
前言
归并排序是分治法的经典应用，时间复杂度稳定 O(n log n)。
一、分治思想
1.分解 2.递归排序 3.合并
二、代码实现
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 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.extend(left[i:])
result.extend(right[j:])
return result三、复杂度
时间 O(n log n)，空间 O(n)，稳定
四、应用
链表排序、外部排序、求逆序对
总结
归并排序性能稳定，适合大规模数据。
下一篇：快速排序
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
