MyException - 我的反常网
当时方位:我的反常网» 归纳 » 十大编程算法助程序员走上高手之路

十大编程算法助程序员走上高手之路

www.x8vin4.com  网友共享于:2015-02-04  阅读:0次

算法一:快速排序算法

快速排序是由东尼·霍尔所开展的一种排序算法。在均匀状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需求Ο(n2)次比较,但这种状况并不常见。事实上,快速排序一般显着比其他Ο(n log n) 算法更快,由于它的内部循环(inner loop)能够在大部分的架构上很有功率地被完结出来。

快速排序运用分治法(Divide and conquer)战略来把一个串行(list)分为两个子串行(sub-lists)。

算法进程:

1 从数列中挑出一个元素,称为 “基准”(pivot),

2 从头排序数列,一切元素比基准值小的摆放在基准前面,一切元素比基准值大的摆在基准的后边(相同的数能够就任一边)。在这个分区退出之后,该基准就处于数列的中心方位。这个称为分区(partition)操作。

3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部景象,是数列的巨细是零或一,也便是永久都现已被排序好了。尽管一向递归下去,可是这个算法总会退出,由于在每次的迭代(iteration)中,它至少会把一个元素摆到它终究的方位去。

快速排序算法


算法二:堆排序算法

堆排序(Heapsort)是指运用堆这种数据结构所规划的一种排序算法。堆积是一个近似彻底二叉树的结构,并一起满意堆积的性质:即子结点的键值或索引总是小于(或许大于)它的父节点。

堆排序的均匀时刻杂乱度为Ο(nlogn) 。

算法进程:

创立一个堆H[0..n-1]

把堆首(最大值)和堆尾交换

3. 把堆的尺度缩小1,并调用shift_down(0),意图是把新的数组顶端数据调整到相应方位

4. 重复进程2,直到堆的尺度为1

堆排序算法


算法三:归并排序

归并排序(Merge sort,台湾译作:兼并排序)是建立在归并操作上的一种有用的排序算法。该算法是选用分治法(Divide and Conquer)的一个十分典型的运用。

算法进程:

1. 请求空间,使其巨细为两个现已排序序列之和,该空间用来寄存兼并后的序列

2. 设定两个指针,开端方位分别为两个现已排序序列的开端方位

3. 比较两个指针所指向的元素,挑选相对小的元素放入到兼并空间,并移动指针到下一方位

4. 重复进程3直到某一指针抵达序列尾

5. 将另一序列剩余的一切元素直接复制到兼并序列尾

归并排序


算法四:二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的查找算法。搜素进程从数组的中心元素开端,假如中心元素正好是要查找的元素,则搜 素进程完毕;假如某一特定元素大于或许小于中心元素,则在数组大于或小于中心元素的那一半中查找,并且跟开端相同从中心元素开端比较。假如在某一进程数组 为空,则代表找不到。这种查找算法每一次比较都使查找规划缩小一半。减半查找每次把查找区域削减一半,时刻杂乱度为Ο(logn) 。


算法五:BFPRT(线性查找算法)

BFPRT算法处理的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,经过奇妙的分 析,BFPRT能够确保在最坏状况下仍为线性时刻杂乱度。该算法的思维与快速排序思维类似,当然,为使得算法在最坏状况下,仍然能抵达o(n)的时刻杂乱 度,五位算法作者做了精妙的处理。

算法进程:

1. 将n个元素每5个一组,分红n/5(上界)组。

2. 取出每一组的中位数,恣意排序办法,比方插入排序。

3. 递归的调用selection算法查找上一步中一切中位数的中位数,设为x,偶数个中位数的状况下设定为选取中心小的一个。

4. 用x来切割数组,设小于等于x的个数为k,大于x的个数即为n-k。

5. 若i==k,回来x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。

停止条件:n=1时,回来的便是i小元素。


算法六:DFS(深度优先查找)

深度优先查找算法(Depth-First-Search),是查找算法的一种。它沿着树的深度遍历树的节点,尽或许深的查找树的分 支。当节点v的一切边都己被探寻过,查找将回溯到发现节点v的那条边的开端节点。这一进程一向进行到已发现从源节点可达的一切节点停止。假如还存在未被发 现的节点,则挑选其间一个作为源节点并重复以上进程,整个进程重复进行直到一切节点都被拜访停止。DFS归于盲目查找。

深度优先查找是图论中的经典算法,运用深度优先查找算法能够发生方针图的相应拓扑排序表,运用拓扑排序表能够便利的处理许多相关的图论问题,如最大途径问题等等。一般用堆数据结构来辅佐完结DFS算法。

深度优先遍历图算法进程:

1. 拜访极点v;

2. 顺次从v的未被拜访的邻接点动身,对图进行深度优先遍历;直至图中和v有途径相通的极点都被拜访;

3. 若此刻图中尚有极点未被拜访,则从一个未被拜访的极点动身,从头进行深度优先遍历,直到图中一切极点均被拜访过停止。

上述描绘或许比较笼统,举个实例:

DFS 在拜访图中某一开端极点 v 后,由 v 动身,拜访它的任一邻接极点 w1;再从 w1 动身,拜访与 w1邻 接但还没有拜访过的极点 w2;然后再从 w2 动身,进行类似的拜访,… 如此进行下去,直至抵达一切的邻接极点都被拜访过的极点 u 停止。

接着,退回一步,退到前一次刚拜访过的极点,看是否还有其它没有被拜访的邻接极点。假如有,则拜访此极点,之后再从此极点动身,进行与前述类似的拜访;假如没有,就再退回一步进行查找。重复上述进程,直到连通图中一切极点都被拜访过停止。


算法七:BFS(广度优先查找)

广度优先查找算法(Breadth-First-Search),是一种图形查找算法。简略的说,BFS是从根节点开端,沿着树(图)的宽度遍历树(图)的节点。假如一切节点均被拜访,则算法间断。BFS相同归于盲目查找。一般用行列数据结构来辅佐完结BFS算法。

算法进程:

1. 首先将根节点放入行列中。

2. 从行列中取出第一个节点,并查验它是否为方针。

假如找到方针,则完毕查找并回传成果。

不然将它一切没有查验过的直接子节点参加行列中。

3. 若行列为空,表明整张图都检查过了——亦即图中没有欲查找的方针。完毕查找并回传“找不到方针”。

4. 重复进程2。

BFS(广度优先查找)


算法八:Dijkstra算法

戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰核算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法运用了广度优先查找处理非负权有向图的单源最短途径问题,算法终究得到一个最短途径树。该算法常用于路由算法或许作为其他图算法的一个子模块。

该算法的输入包括了一个有权重的有向图 G,以及G中的一个来历极点 S。咱们以 V 表明 G 中一切极点的调集。每一个图中的边,都是两个极点所构成的有序元素对。(u, v) 表明从极点 u 到 v 有途径相连。咱们以 E 表明G中一切边的调集,而边的权重则由权重函数 w: E → [0, ∞] 界说。因而,w(u, v) 便是从极点 u 到极点 v 的非负权重(weight)。边的权重能够想像成两个极点之间的间隔。任两点间途径的权重,便是该途径上一切边的权重总和。已知有 V 中有极点 s 及 t,Dijkstra 算法能够找到 s 到 t的最低权重途径(例如,最短途径)。这个算法也能够在一个图中,找到从一个极点 s 就任何其他极点的最短途径。关于不含负权的有向图,Dijkstra算法是现在已知的最快的单源最短途径算法。

算法进程:

1. 初始时令 S={V0},T={其他极点},T中极点对应的间隔值

若存在<v0,vi>,d(V0,Vi)为<v0,vi>弧上的权值

若不存在<v0,vi>,d(V0,Vi)为∞

2. 从T中选取一个其间隔值为最小的极点W且不在S中,参加S

3. 对其他T中极点的间隔值进行修正:若加进W作中心极点,从V0到Vi的间隔值缩短,则修正此间隔值

重复上述进程2、3,直到S中包括一切极点,即W=Vi停止

Dijkstra算法


算法九:动态规划算法

动态规划(Dynamic programming)是一种在数学、核算机科学和经济学中运用的,经过把原问题分解为相对简略的子问题的办法求解杂乱问题的办法。 动态规划常常适用于有堆叠子问题和最优子结构性质的问题,动态规划办法所耗时刻往往远少于朴素解法。

动态规划背面的基本思维十分简略。大致上,若要解一个给定问题,咱们需求解其不同部分(即子问题),再兼并子问题的解以得出原问题的解。 一般许多 子问题十分类似,为此动态规划法企图仅仅处理每个子问题一次,然后削减核算量: 一旦某个给定子问题的解现已算出,则将其回忆化存储,以便下次需求同一个 子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规划呈指数增加时特别有用。

关于动态规划最经典的问题当属背包问题。

算法进程:

1. 最优子结构性质。假如问题的最优解所包括的子问题的解也是最优的,咱们就称该问题具有最优子结构性质(即满意最优化原理)。最优子结构性质为动态规划算法处理问题供给了重要头绪。

2. 子问题堆叠性质。子问题堆叠性质是指在用递归算法自顶向下对问题进行求解时,每次发生的子问题并不总是新问题,有些子问题会被重复核算屡次。 动态规划算法正是运用了这种子问题的堆叠性质,对每一个子问题只核算一次,然后将其核算成果保存在一个表格中,当再次需求核算现已核算过的子问题时,仅仅 在表格中简略地检查一下成果,然后获得较高的功率。


算法十:朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种根据贝叶斯定理的简略概率分类算法。贝叶斯分类的根底是概率推理,便是在各种条件的存在不确定,仅知其呈现概率的状况下, 怎样完结推理和决议计划使命。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是根据独立假定的,即假定样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依托准确的天然概率模型,在有监督学习的样本会集能获获得十分好的分类作用。在许多实践运用中,朴素贝叶斯模型参数估量运用最大似然估量办法,换言之朴素贝叶斯模型能作业并没有用到贝叶斯概率或许任何贝叶斯模型。

文章谈论

那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
60个开发者不容错失的免费资源库
60个开发者不容错失的免费资源库
我是怎样打败延迟症的
我是怎样打败延迟症的
程序员应该重视的一些事儿
程序员应该重视的一些事儿
看13位CEO、开创人和高管怎样进步作业功率
看13位CEO、开创人和高管怎样进步作业功率
每天作业4小时的程序员
每天作业4小时的程序员
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序猿的兴起——Growth Hacker
程序猿的兴起——Growth Hacker
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
什么才是优异的用户界面规划
什么才是优异的用户界面规划
“懒”出功率是程序员的美德
“懒”出功率是程序员的美德
程序员周末都喜爱做什么?
程序员周末都喜爱做什么?
那些争议最大的编程观念
那些争议最大的编程观念
团队中“技能大拿”并非越多越好
团队中“技能大拿”并非越多越好
程序员都该阅读的书
程序员都该阅读的书
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
老美怎样看待阿里赴美上市
老美怎样看待阿里赴美上市
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
漫画:程序员的作业
漫画:程序员的作业
总结2014我国互联网十大段子
总结2014我国互联网十大段子
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
一个程序员的时刻办理
一个程序员的时刻办理
程序员最惧怕的5件事 你中招了吗?
程序员最惧怕的5件事 你中招了吗?
游览,写作,编程
游览,写作,编程
科技史上最臭名远扬的13大罪犯
科技史上最臭名远扬的13大罪犯
Java程序员必看电影
Java程序员必看电影
 程序员的姿态
程序员的姿态
程序员的轻视链
程序员的轻视链
初级 vs 高档开发者 哪个性价比更高?
初级 vs 高档开发者 哪个性价比更高?
程序员眼里IE阅读器是什么样的
程序员眼里IE阅读器是什么样的
5款最佳正则表达式修改调试器
5款最佳正则表达式修改调试器
怎样成为一名黑客
怎样成为一名黑客
2013年我国软件开发者薪资调查报告
2013年我国软件开发者薪资调查报告
怎样差异一个程序员是“内行“仍是“新手“?
怎样差异一个程序员是“内行“仍是“新手“?
我的老公是个程序员
我的老公是个程序员
中美印日四国程序员比较
中美印日四国程序员比较
Web开发者需具有的8个好习惯
Web开发者需具有的8个好习惯
10个调试和排错的小主张
10个调试和排错的小主张
程序员和编码员之间的差异
程序员和编码员之间的差异
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我换岗是由于他们的显示器更大
我换岗是由于他们的显示器更大
老程序员的下场
老程序员的下场
写给自己也写给你 自己究竟该何去何从
写给自己也写给你 自己究竟该何去何从
做程序猿的老婆应该留意的一些工作
做程序猿的老婆应该留意的一些工作
代码女神横空出世
代码女神横空出世
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
软件开发程序过错反常ExceptionCopyright © 2009-2015 MyException 版权一切