基础算法

来自软件实验室
跳转至: 导航搜索

排序

  • 最快最简单的排序--桶排序
     直观的说,使用一个适当长度的一维数组,当数字出现一次的时候,就将对应数组下标的值加1,最后直接输出数组中非零值的数组下标,即为桶排序!
代码如下: 文件:BucketSimple.c
  • 选择排序
     基本思想就是:每次遍历,只选择最值元素进行交换,这样一次遍历,只需进行一次交换即可,从而避免了其它无价值的交换操作。
     具体方法为:
     遍历一次,记录下最值元素所在位置,遍历结束后,将此最值元素调整到合适的位置
     这样一次遍历,只需一次交换,便可将最值放置到合适位置
     文件:ChooseSort.c
  • 冒泡排序
     冒泡排序的基本思想是,每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来!
代码如下: 文件:BubbleSort.c
  • 快速排序
     快速排序采用的思想是分治思想。
     快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速   排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
      举例说明一下吧,这个可能不是太好理解。假设要排序的序列为
       2 2 4 9 3 6 7 1 5 首先用2当作基准,使用i j两个指针分别从两边进行扫描,把比2小的元素和比2大的元素分开。首先比较2和5,5比2大,j左移
       2 2 4 9 3 6 7 1 5 比较2和1,1小于2,所以把1放在2的位置
       2 1 4 9 3 6 7 1 5 比较2和4,4大于2,因此将4移动到后面
       2 1 4 9 3 6 7 4 5 比较2和7,2和6,2和3,2和9,全部大于2,满足条件,因此不变
       经过第一轮的快速排序,元素变为下面的样子
       [1] 2 [4 9 3 6 7 5]
     之后,在把2左边的元素进行快排,由于只有一个元素,因此快排结束。右边进行快排,递归进行,最终生成最后的结果。
代码如下: 文件:QKSORT.c


搜索

  • 深度优先搜索
   最直观的例子是,往盒子中放置扑克牌。
   假设你手中有三张扑克牌,前面有三个盒子,将这三张牌放入盒子中,有多少排列组合?首先先将三张牌随机放入三个盒子,放完后后续没有盒子了。
然后回到第三个盒子取出牌,再回到第二个盒子取出牌,这时你手中有两张牌。再按照与第一次放牌顺序不同的方式往两个盒子中再放一次,形成另外一种不同的放牌组合。
这个算法用到了递归的思想。伪算法演示: //深度优先搜索的基本模型 void dfs(int step) { 判断边界 尝试每一种可能 for(i=1;i<=n;i++) { 继续下一步,有个递归调用dfs(step+1); } 返回 } 代码如下: 文件:DFS.c


  • 广度优先搜索
   如果说,深度优先搜索是一条道走到黑,广度优先搜索就是在每一个层面上先考虑周全后再走向下一个层面。
典型的应用就是走迷宫,从第一个点开始,向各个方向找可走的路径,未碰到障碍物就是可走的路径,若碰到障碍物就是不可走的路径。
一层一层的走下来,直到到达最后的目的地! 代码如下: 文件:BFS.c

最短路径

  • Flyod-Warshall算法 -- 解决多源最短路径问题
   举个例子的话,就是求任意两个城市之间的最短路程,先将图中各个点转换为矩阵存储。
   FW.png
   当两点之间不允许经过第三个点时,上面右图显示的就是这些城市之间的最短路程,即为初始路程。
   
   假如现在只允许经过1号顶点,求任意两点间的最短路程,只需要判断e[i][1]+e[1][j]是否比e[i][j]要小即可。
   
   假如现在允许经过1和2号顶点,在1号顶点求得的结果的基础上,再判断经过2号顶点时是否可以可以使得i号顶点到j号顶点之间的路程
变得更短,即判断e[i][2]+e[2][j]是否比e[i][j]要小。 。。。。。。。。 最后允许通过所有顶点作为中转,在求一次, 核心代码如下: // Floyed-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j] = e[i][k]+e[k][j]; 代码如下: 文件:Zuiduanlujing Floyd Warshall.c 注意:该算法不能解决带有负权回路的问题,即在测试的时候,路径值必须为正!
  • Dijkstra算法 -- 解决单源最短路径问题
   先上一张图:
   Disjkstra1.png
   接下来继续在剩下的3,4,5,6号顶点中,以上图中提到的方式继续“松弛”,即可得到1号顶点到其余各个顶点的最短路径的数组。
   该算法的基本思想是,每次找到离源点(即上图的1号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,
最终得到其余所有点的最短路径。 完整算法如下: 文件:Dijkstra.c 注意:该算法不能解决带有负权回路的问题,即在测试的时候,路径值必须为正!
  • Bellman-Ford算法
   Bellman-Ford算法和上面Dijkstra算法同是解决单源最短路径问题的算法,但是Bellman-Ford解决了带有负权边的图的问题!
   先上一张图:
   Bellman Ford.png
   在上图的基础上,我们可以这样去解释,第一轮在对所有的边进行松弛后,得到的是从1号顶点只经过一条边
   到达其余各顶点的最短路径的长度。第二轮在对所有的边进行松弛之后,得到的是从1号顶点最多经过两条边,
   到达其余各顶点的最短路径长度。如果现在进行k轮的话,得到的就是1号顶点最多经过k条边到达其余各个顶点的最短路径长度。
   基本算法:
   文件:Bellman Ford 1.c
   两种算法优化:
   文件:Bellman Ford optimization.c   优化思路就是:每次仅对最短路径估计值发生了变化的顶点的所有出边松弛操作。