总结

作者: 小翼龙 | 来源:发表于2018-06-21 11:55 被阅读0次

    1、二叉树广度遍历(非递归)

    广度遍历非递归实现需要依靠一个队列。

    2、二叉树深度遍历(递归与非递归,前序,中序和后序)

    递归前序(根左右):

    前序非递归:

    递归中序(左根右):

    中序非递归:

    递归后序(左右根):

    非递归后序:二叉树的后序遍历--非递归实现 - 小雨淅淅 - 博客园

    3、查找算法

    顺序查找(一个个的挨着找)

    二分查找(前提,数列有序,假设递增)

    插值查找

    对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。

    斐波那契查找

    二分查找、插值查找和斐波那契查找都只适用于数列有序,本质上是类似的,只是分割点选择不同。他们的时间复杂度是一样的,只是适用场景不同,在特定的场景下某种算法更优。

    线性索引查找,分为稠密索引、分块索引和倒排索引。稠密索引是指对每个记录都建立一个数据项,空间消耗比较大。分块索引,块间有序,块内无序。

    哈希查找:通过哈希函数建立哈希表。哈希表就是一种以键-值存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。

    树表查找,分为二叉查找树,

    二叉查找树,也叫二叉排序树,要求左子树的值小于根节点,右子树的值大于根节点,同时左右子树也都是二叉查找树。它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡。可以递归非递归两种方式实现。二叉查找树的中序遍历结果就是一个递增数列,最小值是二叉树最左边的值,最大值是二叉树最右边的值。

    2-3查找树

    2-3树的查找效率与树的高度是息息相关的。在最坏的情况下,也就是所有的节点都是2-node节点,查找效率为lgN;在最好的情况下,所有的节点都是3-node节点,查找效率为log3N约等于0.631lgN

    红黑树由2-3树演变而来,红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

    红色节点向左倾斜

    一个节点不可能有两个红色链接

    整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

    七大查找算法 - AI你一生 - 博客园

    4、排序算法

    直接插入排序(将无序数列第一个插入到有序数列中)

    希尔排序是直接插入排序的一种改进

    冒泡排序:

    快速排序

    直接选择排序

    堆排序

    【c++】STL里的priority_queue用法总结 - CSDN博客

    归并排序

    5、贪心算法、回溯法、动态规划

    相关文章

      网友评论

          本文标题:总结

          本文链接:https://www.haomeiwen.com/subject/rweseftx.html