ABOUT US

ABOUT US

大侠且慢,五大编程算法留下可好?

PubDate:2016-05-16Author:Sources:Views:3338

无算法不编程,程序猿行走江湖,算法是少不了的“武器”。

算法用得好,代码自减少。

算法用的妙,bug无处闹。


【算法1】:快速排序算法

采用分治法策略把一个List分为两个sub-list。

1 )从数列中挑出一个元素,作为“基准”;

2) 重新排序数列,元素中比基准小的数值放在基准前面,元素中比基准大的数值放在基准后面;

3 )最后把重新排序的数列(小于基准的子数列和大于基准的子数列),进行递归。


【算法2】:堆排序算法

一个近似二叉树的结构,满足子节点的键值或索引总小于(或大于)它的父节点。

1)创建一个堆,定义为H[0..n-1],把堆首和堆尾互换(即最大值和最小值互换);

2)把堆的尺寸设置为1,调用shift_down(0)方法,把新数组顶端的数据调整到相应位置;

3)重复步骤2,直到堆的尺寸为1。


【算法3】:归并排序

归并排序是采用分治法的典型应用。

1) 申请一个足够的空间,用于存放合并后的序列(大小为两个已排序的序列之和);

2)设定两个指针,初始位置指向两个已排序序列的起始位;

3)对比两个指针所指向的元素,将小的元素放入合并空间,指针移动至下一个位置;

4)重复步骤3,直至某一指针移到序列末尾;

5)将另一序列中剩下的元素复制到合并序列末尾。


【算法4】:BFS(广度优先搜索)

广度优先搜索,是从根节点开始沿着树的宽度遍历树的节点,如果所有节点都被访问了,算法终止;

1)首先,根节点需放在队列中。

2)从队列中取出第一个节点,并检测它是否所求目标。

如果是,则结束搜寻并回传结果。

否则,将它所有没检测过的直接子节点加入队列中。

3)若队列为空,结束搜寻并回传“找不到目标”。

4)重复步骤2。


【算法5】:Dijkstra算法

使用广度优先搜索,解决非负权有向图的单源最短路径问题,得到一个最短路径树。

1) 初始时令有向图G中有顶点 S和T,S={V0},T={其余顶点},T中顶点对应的距离值d;

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

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

2)从T中选择一个其距离值是最小的顶点W,且不能在S中,加入S;

3) 对其余T中顶点的距离值进行修改:

若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值;

4)重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止



分享到: