十大经典排序算法之归并排序
归并排序
前面的时候讲了一些时间复杂度是
的排序算法，虽然希尔排序不是
的排序算法，但是在真正的实际应用中还是比较少的，因为相对来说，排序所需的时间比较长。
今天我就给你介绍另外一种排序算法，归并排序算法。它的时间复杂度是
, 而且是稳定的排序算法，唯一美中不足的一点是它不是原地排序算法，需要使用额外的存储空间。
归并排序，采用的是分而治之的思想，将要排序的区间一分为二，当左右区间都有序后，就相当于对两个有序数组进行合并。那怎样左右区间的元素才能有序呢？这就需要再一次进行一分为二了，当左、右区间的元素只有一个的时候，自然而然就是有序的了。
从上面的描述，我们可以看出，这是一个不断将大问题划分为小问题的过程，这不正是递归算法的精髓所在嘛。没错，归并排序算法一般都是基于递归进行实现的。
好了，接下来，看下动画演示。
代码实现
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def merge_sort(array: List[int]) -> None:
_merge_sort_(array, 0, len(array)-1)
def _merge_sort_(array: List[int], low: int, high: int) -> None:
if low < high:
mid = low + ((high - low) >> 1)
_merge_sort_(array, low, mid)
_merge_sort_(array, mid+1, high)
_merge(array, low, mid, high)
def _merge(array: List[int], low: int, mid: int, high: int):
# array[low:mid], array[mid, high] are sorted
tmp = []
i, j = low, mid+1
while i <= mid and j <= high:
if array[i] <= array[j]:
tmp.append(array[i])
i += 1
else:
tmp.append(array[j])
j += 1
if i <= mid:
tmp.extend(array[i:mid+1])
else:
tmp.extend(array[j:high+1])
array[low:high+1] = tmp
if __name__ == "__main__":
array1 = [3, 5, 6, 7, 8]
array2 = [2, 2, 2, 2]
array3 = [4, 3, 2, 1]
array4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
merge_sort(array1)
print(array1)
merge_sort(array2)
print(array2)
merge_sort(array3)
print(array3)
merge_sort(array4)
print(array4)
延伸思考
归并排序除了作为一种排序算法，合并两个有序数组的操作同样是非常经典的，而且在面试求职过程中会经常用到的。
归并排序里面是合并两个有序的数组，还可以合并两个有序的链表、合并 k 个链表等等。
LeetCode 上具体的题目链接有：
- 88. 合并两个有序数组
- 1669. 合并两个链表
- 21. 合并两个有序链表
- 23. 合并K个升序链表
总结
归并排序是非常高效的排序算法。
时间复杂度数
,无论要排序的数据是什么样的，性能都是稳定的。
空间复杂度是
另外，合并操作是非常高效且常用的操作，值得我们学习体会。
如果有其他的问题，可以在添加我的微信，欢迎一起交流学习。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-02-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录