关于尚航
ABOUT US
大侠且慢,五大编程算法留下可好?
无算法不编程,程序猿行走江湖,算法是少不了的“武器”。
算法用得好,代码自减少。
算法用的妙,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为止