【数据结构与算法】归并排序的原理及算法实现
2023-09-27 14:21:04 时间
归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组
将数组分解到最小之后,合并两个有序的数组,基本思路就是比较两个数组最前面的数字,谁小就先取谁,取了后相应的指针就往后移动一位。然后再比较,知道一个数组为空,最后把一个数组的剩余部分复制过来即可
基本实现
1.有一串数组如下,将其对半分成两个数组。
2.左右继续拆分到每一个子部分只有一个元素,如下,拆分到只有一个子元素的之后拆分结束
3,拆分完之后进行合并,56跟26是上面绿色框拆出来的,合并的时候采用小的在前,大的在后。
4.把两个绿色块进行合并,这个时候就要借助定义的游标了,一个指的是左边大部分Left ,一个是右边的Right.合并的时候采用的方式是,对于左边的部分有一个游标,右边的部分也有一个游标,然后对于所指的两个部分进行比较换位。
5.经过比较17比较小,拿出来,之后Right向后移动一位。
6.之后继续比较Right的指向比26大,取出26,Left继续向后移动一位。之后比较发现Right指向比Left大,取出54,最后把Right放到后面,得到下面的一个有序数列。
7.右边继续采用相同的方式,的得到两个部分,之后现在对于整个序列来说就只有两个部分了。
8.按照上面相同的方式对两个绿色框的数据进行合并。依旧是左边的游标Left,右边的右边Right对比。得到了一个有序的数列
这个就是归并算法的思想:把一组元素一直拆分到只有一个子元素,之后开始合并,通过Left与Right进行排序。
那么对于奇数个也是一样的,只不过拆分的时候最后的的一组多出来一个。合并的时候也是,先把最后那个灰色框那两个合并到一起,再跟44合并成3个,怎么拆的就怎么合并。
归并算法代码实现
'''
Create by YO
@Time: 2020/4/22
'''
#相除的时候两个斜杠无小数部分。向下取整
def merge_sort(alist):
'''归并排序'''
n=len(alist)
if n<=1:
return alist
mid=n//2 #中间值
left_li=merge_sort(alist[:mid])
#right 采用归并排序后形成的新的列表
right_li=merge_sort(alist[mid:])
#将两个有序的子序列合并成一个新的整体 merge(left,right) 左边的指针跟右边的指针都指向两个子序列的第一个元素
left_pointer,right_pointer=0,0
result=[]
while left_pointer<len(left_li) and right_pointer<len(right_li):
if left_li[left_pointer]<right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer+=1 #移动完向后一位移动
else:
result.append(right_li[right_pointer])
right_pointer+=1
result+=left_li[left_pointer:]
result+=right_li[right_pointer:]
return result
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
sorted_li=merge_sort(li)
print(li)
print(sorted_li)
输出:
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
时间复杂度
最优时间复杂度:O(nlogn)
最坏时间复杂度:O(nlogn)
稳定性:稳定
相关文章
- 【MATLAB教程案例32】基于matlab的交通标志检测分割算法的仿真——形态学处理,膨胀,腐蚀,形状检测,颜色模型,小波滤波等知识的综合应用
- 【C++】STL中sort算法使用了什么排序算法?
- C#,快速排序算法(Quick Sort)的递归实现与数据可视化
- 视觉直观感受7种常用的排序算法
- 排序算法--鸽巢排序(PigeonholeSort)的原理、排序思路、适用场景及代码示例
- 排序算法--希尔排序(ShellSort)的原理、排序思路、适用场景及代码示例
- 数据结构算法第一篇排序算法常见
- 一篇文章学会Java十大排序算法
- [算法]快速排序,归并排序,堆排序的数组和单链表实现
- [算法]循环打印矩阵,蛇形矩阵专题
- 排序算法系列之(四)——抓扑克牌风格的插入排序
- 排序算法系列之(三)——略显神秘的快速排序
- 蓝桥杯《算法很美》第3章:排序与查找
- Java程序员必须掌握的8大排序算法
- LeetCode384之打乱数组(相关话题:随机算法,洗牌算法)
- 华为OD机试 - 寻找密码(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 【每日算法】排序算法总结(复杂度&稳定性)
- 动画+原理+代码,解读十大经典排序算法
- 【算法专题】秒懂八种排序算法的原理
- 算法初学者指南
- 算法-排序算法
- 前端排序算法 - 选择排序算法 (4)
- 前端排序算法 - 归并排序算法 (1)
- 36数据结构与算法分析之---拓扑排序
- leetcode算法108.将有序数组转换为二叉搜索树