欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

经典算法之归并排序——python和JS实现

程序员文章站 2022-07-10 21:35:17
前言 文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理。 作者:韩忠康 PS:如有需要Python学习资料的小伙伴可以加点击下方链接自行获取http://t.cn/A6Zvjdun 算法 归并排序(merge-sort),典型的分治策 ......
经典算法之归并排序——python和JS实现

 

前言

文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理。

作者:韩忠康

ps:如有需要python学习资料的小伙伴可以加点击下方链接自行获取http://t.cn/a6zvjdun

算法

归并排序(merge-sort),典型的分治策略(divide and conquer)。核心思路是将整体序列一分为二形成两个子序列,分别对子序列排序,再将两个有序子序列合并成一个有序序列。

思路如图:

经典算法之归并排序——python和JS实现

 

整体过程分为拆分和合并两大阶段。

拆分,核心问题是确定拆分位置即可,我们利用左右元素索引之和除2即可,也就是:mid = (left + right)/2,指导拆分到子序列仅仅存在一个元素的基本情形。

合并,merge 是归并排序的核心,将两个已排序子序列合并为一个排序序列的过程。当子序列中仅存在一个元素时,可视为子序列已经排序,因此我们的合并是从两个单一元素子序列开始的。当子序列存在多个元素时,我们需要逐个得到当前最小元素,进而完成整体排序,过程中我们需要一个临时区来存储已排序的部分。

合并思路如下图所示,我们以合并 [2, 3, 5, 6, 8] 和 [0, 1, 4, 7, 9] 为例,进行演示:

经典算法之归并排序——python和JS实现

 

如图,实现时,设置 i,j 分别存储两个子序列待比较元素索引。比较后,将小元素移动到临时区,同时右移索引。当其中一个子序列全部元素全部移动到临时区后,另一个子序列将后续元素直接移动到临时区即可,不需要继续比较。最后将临时区已排序数据拷贝回原始序列即可。

python:

经典算法之归并排序——python和JS实现

 

javascript:

经典算法之归并排序——python和JS实现

 

欢迎关注!发送私信“代码”获取源码。

2020年最新python教程:

如果你处于想学python或者正在学习python,python的教程不少了吧,但是是最新的吗?

说不定你学了可能是两年前人家就学过的内容,在这小编分享一波2020最新的python教程。

经典算法之归并排序——python和JS实现

 

 

经典算法之归并排序——python和JS实现

 

 

经典算法之归并排序——python和JS实现

 

 

经典算法之归并排序——python和JS实现

 

 

以上这些教程小编已经为大家打包准备好了,希望对正在学习的你有所帮助!

获取方式,私信小编 “ 资料 ”,即可免费获取哦!