GitHub超6.8万星,最全Python入门算法来了(下)

简介: Github上超过6.8万星标:最全算法及Python实现。该项目的算法包括排序、搜索等经典算法,描述较为详细,对算法原理本身、应用场景以及实现过程的可视化等。

堆排序


堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。


代码实现:

https://www.toptal.com/developers/sorting-algorithms/heap-sort


基数排序


基数排序(英语:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。


选择排序


7.gif

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。


代码实现:

https://www.toptal.com/developers/sorting-algorithms/selection-sort


希尔排序




8.gif


希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。
希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的:


  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位


代码实现:

https://www.toptal.com/developers/sorting-algorithms/shell-sort


拓扑排序


在计算机科学领域,有向图的拓扑排序是其顶点的线性排序,使得对于从顶点u到顶点v的每个有向边uv,u在排序中都在v之前。例如,图形的顶点可以表示要执行的任务,并且边可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中,拓扑排序只是一个有效的任务顺序。 如果且仅当图形没有定向循环,即如果它是有向无环图(DAG),则拓扑排序是可能的。任何DAG具有至少一个拓扑排序,并且已知这些算法用于在线性时间内构建任何DAG的拓扑排序。


搜索算法


线性搜索




9.gif

线性搜索或顺序搜索是一种寻找某一特定值的搜索算法,指按一定的顺序检查数组中每一个元素,直到找到所要寻找的特定值为止。是最简单的一种搜索算法。


二分搜索算法

100.png

二分搜索(英语:binary search),也称折半搜索(英语:half-interval search),对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。


插值搜索算法


插值查找(Interpolation Search)是根据要查找的关键字key与顺序表中最大、最小记录的关键字比较后的查找方法,它假设输入数组是线性增加的(这个假设的精确度会影响算法的效率,但不会影响算法的正确性)。


跳跃搜索算法


跳跃搜索算法(Jump Search)跟二分查找算法类似,它也是针对有序序列的查找,只是它是通过查找比较少的元素找到目标。当然它需要通过固定的跳跃间隔,这样它相比二分查找效率提高了很多。


快速选择




11.gif

快速选择(英语:Quickselect)是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的,因而也被称为霍尔选择算法。它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。与快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。


禁忌搜索


禁忌搜索(Tabu Search,TS,又称禁忌搜寻法)是一种现代启发式算法,由美国科罗拉多大学教授Fred Glover在1986年左右提出的,是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案;基于此,算法“移动”到一相邻的方案。经过许多连续的移动过程,提高解的质量。


加密算法


凯撒密码


凯撒密码(英语:Caesar cipher),或称凯撒加密、凯撒变换、变换加密,是一种最简单且最广为人知的加密技术。它是一种替换加密的技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。这个加密方法是以罗马共和时期恺撒的名字命名的,当年恺撒曾用此方法与其将军们进行联系。


维吉尼亚密码


维吉尼亚密码(又译维热纳尔密码)是使用一系列凯撒密码组成密码字母表的加密算法,属于多表密码的一种简单形式。维吉尼亚密码曾多次被发明。该方法最早记录在吉奥万·巴蒂斯塔·贝拉索( Giovan Battista Bellaso)于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的密码》(意大利语:La cifra del. Sig. Giovan Battista Bellaso)中。然而,后来在19世纪时被误传为是法国外交官布莱斯·德·维吉尼亚(Blaise De Vigenère)所创造,因此现在被称为“维吉尼亚密码”。


置换密码


又名取代加密法,是密码学中按规律将文字加密的一种方式。置换密码中可以用不同字母数为一单元,例如每一个或两个字母为一单元,然后再作加密。密文接收者解密时需用原加密方式解码才可取得原文本。由于拼音文字中字的组成为有限的字母,以英语为例只有26个字母,组成可能的单元数较少,因此使用置换密码相对较为容易,而且亦可使用简单机械进行加密;相反,非拼音文字如中文则因单元数非常大难以使用一般加密方式,必需建立密码本,然后逐字替换。更何况某些非拼音文字中字字皆由不同大小的字根来组字,较难转换,因此使用置换密码的示例比较少。


RSA加密算法


RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到当前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。


ROT13算法


ROT13(回转13位,rotate by 13 places,有时中间加了个连字符称作ROT-13)是一种简易的替换式密码。它是一种在英文网络论坛用作隐藏八卦(spoiler)、妙句、谜题解答以及某些脏话的工具,目的是逃过版主或管理员的匆匆一瞥。ROT13被描述成“杂志字谜上下颠倒解答的Usenet点对点体”。(Usenet equivalent of a magazine printing the answer to a quiz upside down.)ROT13 也是过去在古罗马开发的凯撒加密的一种变体。


异或密码


异或密码是密码学中一种简单的加密算法,异或运算符常作为更为复杂的加密算法的组成部分。对于其本身来说,如果使用不断重复的密钥,利用频率分析就可以破解这种简单的异或密码。如果消息的内容被猜出或知道,密钥就会泄露。异或密码值得使用的原因主要是其易于实现,而且计算成本小。简单重复异或加密有时用于不需要特别安全的情况下来隐藏信息。



相关文章
|
1天前
|
数据可视化 API Python
豆瓣评分9.4!堪称经典的Python入门圣经,你还没看过吗?
最理想的新人入门书应该满足两个特点:第一就是内容通俗易懂;第二就是要有实战,能够让读者在学完之后知道具体怎么用。 今天给小伙伴们分享的这份Python入门手册,在为初学者构建完整的Python语言知识体系的同时,面向实际应用情境编写代码样例,而且许多样例还是后续实践项目部分的伏笔。实践项目部分的选题经过精心设计,生动详尽又面面俱到。
|
1天前
|
开发者 Python
GitHub飙升!京东认证的“Python编程入门三剑客”究竟好在哪?
Python凭借着简单易学、功能强大,已经跃居TIOB编程语言榜首,并且已经开始了它的霸榜之旅。如何选择一套适合自己的Python学习教程,是每个Python爱好者面临的首要问题。 今天给小伙伴们带来的是图灵&京东认证的“Python编程入门三剑客”,先看《Python编程从入门到实践》,打好Python入门的底子;再看《Python编程快速上手》,增强用Python处理工作中实际问题的能力;最后看《Python极客项目编程》,用充满想象力的实战案例,充分理解Python编程的奥秘,完成从小白到大神的进化。
|
2天前
|
Linux 网络安全 开发工具
【超详细!超多图!】【代码管理】Python微信公众号开发(3)- 服务器代码上传Github
【超详细!超多图!】【代码管理】Python微信公众号开发(3)- 服务器代码上传Github
|
2天前
|
Python 容器
GitHub狂揽6700 Star,Python进阶必备的案例、技巧与工程实践
当下是 Python 急剧发展的时代,越来越多的人开始学习和使用Pyhon,而大家也遇到了各种问题。这份手册清晰、细致地介绍了 Python 代码应该遵循的编程风格,并解释了背后的原理和机制。
|
2天前
|
数据采集 运维 API
适合所有编程初学者,豆瓣评分8.6的Python入门手册开放下载!
Python是一种跨平台的计算机程序设计语言,它可以用来完成Web开发、数据科学、网络爬虫、自动化运维、嵌入式应用开发、游戏开发和桌面应用开发。 Python上手很容易,基本有其他语言编程经验的人可以在1周内学会Python最基本的内容(PS:没有基础的人也可以直接学习,速度会慢一点) 今天给小伙伴们分享一份Python语言及其应用的手册,这份手册主要介绍 Python 语言的基础知识及其在各个领域的具体应用,基于最新版本 3.x。
|
2天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
7 0
|
2天前
|
算法 Java Go
【经典算法】LeetCode 1103 分糖果 II(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 1103 分糖果 II(Java/C/Python3实现含注释说明,Easy)
8 0
|
2天前
|
存储 算法 Java
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
6 0
|
2天前
|
存储 算法 Java
【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)
4 0
|
6天前
|
算法 程序员 开发工具
GitHub上新!14个Python项目详细教程(附完整代码)
Python作为程序员的宠儿,越来越得到人们的关注,使用Python进行应用程序开发的也越来越多。 今天给小伙伴们分享的这份项目教程完整代码已上传至GitHub,你可以选择跟着这份教程一段一段的手敲出来这几个项目,也可以直接从GitHub上copy下来。