写点什么

python 实现·十大排序算法之归并排序 (Merge Sort)

用户头像
南风以南
关注
发布于: 2020 年 05 月 25 日
python实现·十大排序算法之归并排序(Merge Sort)

简介



归并排序(Merge Sort)是一种非常高效的排序方式,它用了分治的思想,基本排序思想是:先将整个序列两两分开,然后每组中的两个元素排好序。接着就是组与组和合并,只需将两组所有的元素遍历一遍,即可按顺序合并。以此类推,最终所有组合并为一组时,整个数列完成排序。

算法实现步骤



  1. 把长度为n的输入序列分成两个长度为n/2的子序列;

  2. 对这两个子序列分别采用递归的进行排序;

  3. 将两个排序好的子序列的元素拿出来,按照顺序合并成一个最终的序列,即可完成排序。

Python 代码实现



# merge_sort 代码实现
from typing import List
def merge(arr1:List[int], arr2:List[int]):
result = []
while arr1 and arr2:
if arr1[0] < arr2[0]:
result.append(arr1.pop(0))
else:
result.append(arr2.pop(0))
if arr1:
result += arr1
if arr2:
result += arr2
return result
def merge_sort(arr:List[int]):
"""
归并排序
:param arr: 待排序的List
:return: 排好序的List
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))



# 测试数据
if __name__ == '__main__':
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("原始数据:", arr)
arr_new = merge_sort(arr)
print("归并排序结果:", arr_new)



# 输出结果
原始数据: [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
归并排序结果: [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

动画演示

算法分析

  • 时间复杂度

归并排序时间复杂度计算公式:排序总时间=子序列排序时间+合并时间。

假设一个序列有个数的排序时间为,那么

由于合并时,两个子序列已经组内排好序了,将两个排好序的序列组合成一个大的有序序列,时间复杂度为,则有:

递归推导可得出:

时,递归结束,此时有:

所以归并排序的时间复杂度为

  • 空间复杂度

每次递归需要用到一个辅助表,长度与待排序的表相等,虽然递归次数是,但每次递归都会释放掉所占的辅助空间,下次递归的栈空间和辅助空间与这部分释放的空间就不相关了,因而空间复杂度为

  • 稳定性

归并排序过程中,能保证相等元素相对位置保持不变,因此为稳定排序。

  • 综合评价

联系我们



个人博客网站:http://www.bling2.cn/

Github地址:https://github.com/lb971216008/Use-Python-to-Achieve

知乎专栏:https://zhuanlan.zhihu.com/Use-Python-to-Achieve

小专栏:https://xiaozhuanlan.com/Use-Python-to-Achieve

博客园:https://www.cnblogs.com/Use-Python-to-Achieve





发布于: 2020 年 05 月 25 日阅读数: 97
用户头像

南风以南

关注

南风以南 2018.11.12 加入

石油开发系研究生

评论

发布
暂无评论
python实现·十大排序算法之归并排序(Merge Sort)