排序算法笔记

1.桶排序:这个算法就好比有11个桶,编号从0~10。每出现一个数,就将对应编号的桶中的放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。(http://blog.jobbole.com/100361/)

优点:速度快

缺点:比较费空间

时间复杂度:O(M+N)

113324mbblb83a3ij09lqf.png

2.冒泡排序:就如同是一个气泡,一步一步往后“翻滚”,直到最后一位。

优点:空间复杂度较小

缺点:时间复杂度较高

时间复杂度:O(N^2)

bubble_sort

3.快速排序:每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。

优点:比冒泡排序效率要高

缺点:最差的情况,复杂度等于冒泡排序

时间复杂度:O(NlogN)

095514cag5fumuqqg5jnsw.png

4.Floyd最短路径算法:最开始只允许经过1号顶点进行中转,接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转,求任意两点之间的最短路程

时间复杂度:O(N^3)

081030is22w3mmnz3r33m3.png

5.Dijkstra最短路径算法:每次找到离源点(上面例子的源点就是1号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径

时间复杂度:O(N2)

090730eq6oqzyq7laqha9y.png

原文地址:https://www.cnblogs.com/xujanus/p/5505864.html