数据结构与算法.xmind

数据结构与算法 排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的数插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角标 找出最大角标后，进行交换 优化思路 同时获取最大值和最小值，然后分别插入数组的首部和尾部 堆排序 思想 使用大顶堆的思想来排序，每次建堆后交换 做法 总体：建堆-替换 建堆 只要左子树或右子树大于当前根节点，则替换 替换后会导致下面的子树发生了变化，因此同样需要进行比较，直至各个节点实现父>子这么一个条件(递归) 交换排序 冒泡排序 思想 每次俩俩交换，将最大值交换到末尾 做法 外层for控制循环次数 内层for控制比较次数 每次循环之后，比较次数都会减少一次 优化思路 如果一趟排序后没有发生位置变化，那么此时就是有序了 快速排序 思想 每次将比支点小的放在支点左边，比支点大的放在支点右边 做法 外循环while只要i和j不碰撞查找 内层两个while循环分别查找出比支点小的和比支点大的角标 如果i<=j满足条件，就交换 一趟排序后，支点的左边都比支点小，支点右边都比支点大 只要满足L<j，i<R就一直执行上面的操作 优化思路 随机选取基准值base(支点随机选取) 配合着使用插入排序(当问题规模较小时，近乎有序时，插入排序表现的很好) 当大量数据，且重复数多时，用三路快排 插入排序 直接插入排序 思想 将数据插入到一个有序的序列中 做法 外层for循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据) 内层while循环加上角标>0的条件查找出要插入的何时位置 退出内层while循环后就找到了合适的位置插入 优化思路 二分查找插入，找合适位置的时候使用二分查找算法 希尔排序 思想 用增量来将数组进行分隔，直到增量为1。底层干的还是插入排序干的活 做法 最外层for外循环控制增量的数量，每次/2 第二层for循环控制每次增量那组开始进行插入排序，直至完毕 第三层while循环找到要插入到哪个位置 归并排序 思想 将两个已排好序的数组合并成一个有序的数组 做法 递归拆分出两个有序的数组，从mid的位置开始拆分，递归出口：只有一个值的时候就不用拆分了 合并两个有序的数据 分别往两个数组填充已有序的数据 比较两个数组的值谁小，谁小就放到我们的数组中 如果比较完之后还有剩余的数据，那么用while直接添加到我们的总数组中 优化思路 当递归到规模足够小时，利用插入排序 归并前判断一下是否还有必要归并 只在排序前开辟一次空间 基数(桶)排序 思想 分配，回收(分配到不同的位置上，然后回收)..不断分配..回收来进行排序，直到有序 做法 分配一个[array.length][10列]的二维数组来装我们的元素 最外层for循环控制要分配和回收的次数(根据最大值) 将元素的个、十、百位依次放到桶子上(第一次就是放个位，第二次放十位) 依据每列回收桶子，两个for循环 外排序 查找算法 二分查找 分块查找 哈希查找 贪心算法 求最小生成树的Prim算法和Kruskal算法 爬山问题 回溯算法 ｎ皇后问题 动态规划Dynamic Planning 应用 求最长公共子序列LCS 矩阵连乘问题 爬楼梯问题 找零问题 0-1背包问题 分治算法Divide and Conquer 应用：归并排序 其它 Rabin fingerprints 文件指纹算法 BitMap 位图算法 BloomFilter 布隆过滤器 线性表 栈 先进后出(LIFO, Last In First Out) 实现 用两个指针域分别指向栈顶和栈底 常见操作 进栈 栈顶本来指向的节点交由新节点来指向 栈顶指针指向新节点 遍历栈 只要栈顶元素的指针不指向栈底，那么就一直输出遍历结果 判断该栈是否为空 只要栈顶和栈底是同一指向，那么该栈就为空 出栈 将栈顶的元素的指针(指向下一个节点)赋值给栈顶指针(完成出栈) 清空栈 栈顶指向栈底，就清空栈了 队列 往往实现静态队列，我们都是做成循环队列 链队列 循环队列 双端队列 Java中的Deque接口 顺序表 链表 单链表 链表是离散存储线性结构 优点 空间没有限制 插入删除元素很快 缺点 存取速度很慢 链表分类 单向链表 一个节点指向下一个节点 双向链表 一个节点有两个指针域 自由主题 循环链表 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环 常见操作 添加数据到链表中 遍历找到尾节点，插入即可(只要while(temp.next != null)，退出循环就会找到尾节点) 遍历链表 从首节点(有效节点)开始，只要不为null，就输出 给定位置插入节点到链表中 首先判断该位置是否有效(在链表长度的范围内) 找到想要插入位置的上一个节点 将原本由上一个节点的指向交由插入的节点来指向 上一个节点指针域指向想要插入的节点 获取链表的长度 每访问一次节点，变量++操作即可 删除给定位置的节点 首先判断该位置是否有效(在链表长度的范围内) 找到想要插入位置的上一个节点 将原本由上一个节点的指向后面一个节点 对链表进行排序 使用冒泡算法对其进行排序 找到链表中倒数第k个节点 不同实现 设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点 (-k+1+链表总数) % 链表总数 查询链表的中间节点 一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点 递归从尾到头输出单链表 只要下面还有数据，那就往下找，递归是从最后往前翻。 反转链表 有递归和非递归两种方式 双向链表 循环链表 树 二叉树 完全二叉树 堆 满二叉树 哈夫曼树 哈夫曼编码 二叉搜索树 AVL树 平衡二叉树 红黑树 多叉树 B树 查找节点 插入节点 删除节点 左旋 B+树 查找节点 插入节点 删除节点 图 分类 有向图 无向图 表示方法 邻接矩阵 邻接表 遍历 深度优先搜索 广度优先搜索 哈希表 哈希函数 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 处理哈希冲突 开放定址法 再哈希法 链地址法 建立一个公共溢出区