Python数据结构与算法学习第七天

1043-李同学

发表文章数:31

热门标签

首页 » 数据结构 » 正文

一.归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。
将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
代码实现:
Python数据结构与算法学习第七天
**代码执行流程:**当输入li = [54,26,93,17,77,31,44,55,20]进入函数后,先计算n=9,mid=4,则alist[:4]=[54,26,93,17],alist[4:]=[31,44,55,20]第一次递归后,计算n=4,mid=2,所以alist[:2]=[54,26],在进行第二次递归,n=2,mid=1,alist[:1]=54,当进行第三地递归时,因为n=1,所以return alist,即left_li=54,而 right_li=merge_sort(alist[1:]),进行递归,因为n=1,所以return alist,即right_li=26,进入循环与判断,最后return result=[26,54],即left_li=[26,54]。接下来进行 right_li=merge_sort(alist[2:]),即完成alist[2:]=[93,17]的排序。结束这个排序后 right_li=[17,93]。然后将现在的left_li=[26,54]与 right_li=[17,93]进行合并,最后为[17,26,54,93],即完成了left_li=alist[:4]=[54,26,93,17]的排序,接下同要完成 right_li=alist[4:]=[31,44,55,20]的排序,同理,结果为[20,31,44,55],再讲left_li=[54,26,93,17]与right_li=[20,31,44,55]进行合并,最后成为有序序列。

二.搜索

搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的,因为该项目是否存在。 搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
Python数据结构与算法学习第七天
代码实现:
Python数据结构与算法学习第七天
上图代码为利用递归的二分法进行查找。
Python数据结构与算法学习第七天
上图为一般方法。

未经允许不得转载:作者:1043-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法学习第七天》 发布于2020-06-16

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录