• 13539426682
  • liuyixi2009@163.com

目录:算法

各种各样的排序(持续更新)

1.冒泡排序

 

思想很明确,就是遇到比自己小的就立刻交换,注意此时比较大的那个(之前在比它小的前面)被转移到了后一位,那么j++后指向的对象就是这个比较大的,如果不是那么 j++ 指向的就是比 j++ 操作前指向的个体大的那个数,从而实现“冒泡”。

 

 

2.选择排序(没用)

 

每次都要遍历一次数组,找到最小的,如果不是原来的就进行交换。

 

 

3.插入排序

 

 

 

 

4.归并排序

 

 

 

 

5.快排

 

 

 

6.桶排序

这个很简单没什么好说的 🙂

 

 

 

7.堆排序

 

思考了很久,事实上堆排序利用的就是最大堆的特性:堆顶的最大值,每次对堆顶的数字进行出堆操作同时放到数组的最后面。而关键的我猛然发现这个数组里面的“键值”,就是x[2]里面的2,可以理解为一种属性(废话),而把这种属性抽象出来就是一种“指针”。可以利用这一点对值进行相关的修改(废话)。像在这个堆排序里面就是这样子,设置了两个“指针”,i和s,i由s生,s又可以变成i,i永远指向s的子节点。

总之很牛皮。

 

 

8.希尔排序:

先粘贴上去,下次再想

 

Bellman-Ford及其队列优化

说白了这玩意可以处理负边权,和 Dijkstra 看起来一样但却有着微妙的不同..

未优化前

优化后

一些分析

可以看的出该算法是以把边扔进去试一试为主,Dijkstra 算法的找最小值那一步体现了它基于贪心,而Bellman-Ford 算法则是从边的点出发,企图通过给定边(u,v)来达到 v 点或者说看能不能缩短源点 s 到 v 的距离(一开始是 inf )。 第一轮把所有边扔进去试,松弛结束后 dis[ ] 数组更新,开始进行第二轮松弛,重新把所有边扔进去算(注意此时会存在冗杂的现象,因为一些点的值已成为确定值)。

事实上可以发现第一次松弛时 dis[ ] 数组只有与源点相邻的点才会更新,而后可以发现第 k 次松弛代表着用 k 条线路可以达到的最小值(即表现为对 dis[ ] 数组的更新)即使出现负边权,设这条蛋疼的边为 x(u,v),则迟早会对 v 进行真正的松弛,(其实第一次把边代进去会缩小 dis[ v ] 的值,就算 dis[ u ] 是 inf , 
dis[ v ] > x(u,v)+ dis[ u ] )我指的真正的松弛是当 dis[ u ] 不为 inf 时,dis[ v ] 再次被更新,然后。。看起来负权边对后续就没什么影响了。。(大概)

而当算了n-1轮后结束,则能给出最短路径。若还能再松弛,则说明出现负权回路。因为若进行了n轮说明了居然存在一条路在通过n个点时的权值比以往的还小,这就说明存在一条路它的值可能为 -100000 之类的,这时就要报错了,这也是Bellman-Ford 的特征:可以处理负权环路。

优化分析

Bellman-Ford算法在每一次实施松弛操作时,就会有一些顶点已经求得最短路径,此后这些顶点的最短路径的估计值就会一直保持不变,不再受后续松弛操作的影响,但是每次还要判断是否需要松弛,这里浪费了大量的时间.

思想:每次选取队首顶点u,对顶点u的所有出边进行松弛操作,例如有一条u->v的边,如果通过u->v的这条边使得源点到顶点v的最短路径变得更短,也即(dis[u] + e[u][v] < dis[v]),并且顶点v不在当前的队列(并用借助一个数组标记顶点是否已经在队列之中),则将顶点v放置队尾. 对顶点u的所有出边松弛完毕之后,就将顶点u出队,接下来不断从队列中取出新的队首顶点反复上面操作直到队列为空结束. 
队列优化的Bellman-Ford的关键之处: 只有那些在前一遍松弛中改变了最短路径估计值的点,才可能引起它们邻接点最短路径估计值发生改变. 因此用一个队列保存被成成功松弛的顶点,之后只对队列中的点进行处理,这就降低了算法的时间复杂度


来自CSDN的说明

说白了就是如果入队成功则代表这个点有资格作为中转站,如果松弛失败了则对它的后续操作是没有意义的,并且可以看到每次把边带进去时是代头指针指向的点的邻边,不会一开始就浪费资源去搞其他边。(大概是这个样子)

(逃

 

Floyd 和 Dijkstra 算法

弗洛伊德算法很简单,疯狂试试就出来了

这个狄克斯特拉就得慢慢找了…

这是Floyd


这是Dijkstra

分析一下这个Dijkstra

先说说这个 Dijkstra ,书上说的所谓“松弛”,其实就是某个点可以用来当中转站这个意思。先找最小的,再以这个最小的点作为中转站然后去扩展(或者说是去“努力”到达【因为可能并不能通过这个点去到达其他点】)其他的点。

这个算法是基于贪心算法而来的,就是说我一直选离我最近的点且保证松弛以后其他点不会离我更近。因此出现负边权就用不了了, 因为每次选取的是当前最短的边进行松弛,当边都是正权时,松弛后边权一定比当前最短边大,所以满足贪心的条件,有了负边后后续的松弛会出现比前边小的情况,不满足贪心的条件所以不能用 Dijkstra 计算带有负边的单源最短路。

总结

1.Floyd 空间复杂度为 N^2 时间复杂度为 N^3

2.Dijkstra 空间复杂度为 M 时间复杂度为 (M+N)logN

分类….