十大排序编程算法.pdf

文档介绍：十大排序编程算法


算法一：快速排序算法
快速排序是由东尼时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到 o(n)的时间复杂 度，
五位算法作者做了精妙的处理。
算法步骤：
n个元素每 5个一组，分成 n/5(上界)组。
，任意排序方法，比如插入排序。
selection算法查找上一步中所有中位数的中位数，设为 x，偶数个中
位数的情况下设定为选取中间小的一个。
x来分割数组，设小于等于 x的个数为 k，大于 x的个数即为 n-k。
i==k，返回 x；若 i<k，在小于 x的元素中递归查找第 i小的元素；若 i>k，在大
于 x的元素中递归查找第 i-k小的元素。
终止条件：n=1时，返回的即是 i小元素。
算法六：DFS（深度优先搜索）
深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历
树的节点，尽可能深的搜索树的分 支。当节点 v 的所有边都己被探寻过，搜索将回溯到发
现节点 v的条边的那 起始节点。这一过程一直进行到已从源节点可达的所有节点为止。
如果还存在未被发 现的节点， 则选择其中一个作为源节点并重复以上过程，整个进程反复
进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑
排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般
用堆数据结构来辅助实现 DFS算法。
深度优先遍历图算法步骤：
点 v；
次从 v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v有路径
相通的顶点都被访问；
此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先
遍历，直到图中所有顶点均被访问过为止。
上述描述可能比较抽象，举个实例：戴克斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯
特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法
最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
该算法的输入包含了一个有权重的有向图 ，G以及