来之不易的暑期留校, 一半献给算法.
第二章 排序
选择排序
- 运行时间和输入的数据无关, 仅和数量有关.
不会利用输入的初始状态 - 数据移动是最少的
我们将研究的其他任何算法 都不具备这个特性…..
插入排序
- 适合小规模数组
- 对于部分有序的数组, 处理起来很有效
- 倒置的数量很少时, 插入排序很可能比其他算法还要快
希尔排序
- 插入排序对于大规模乱序数组很慢, 因为它只会交换相邻元素, 因此为了改进插入排序的局部性,提出了希尔排序
- 希尔排序交换不相邻的元素以对数组的局部性进行排序, 最终用插入排序调整局部有序的数组
归并排序
- 原地归并排序
- 自顶向下 递归实现 分治思想
- 自底向上 从归并微型数组到整体归并
快速排序
- 分治排序算法
堆排序
- 只能说妙啊.. 这本书先讲的优先队列如何实现, 然后紧接着就用sink方法完成了堆排序
稳定性
某地在某时下雨 时间和地点存在对应关系.
按照时间排序后, 再按照地点排序 单个地点的时间排序就很可能被打乱
稳定, 则时间排序没有被打乱. 不稳定, 很可能时间排序被打乱
| 算法 | 是否稳定 | 是否为原地排序 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 选择排序 | 否 | 是 | N^2 | 1 | 最简单粗暴的方式, 交换次数最少 |
| 插入排序 | 是 | 是 | 介于N与N^2 | 1 | 很大程度取决输入元素的排列情况, 如果倒置元素很少则性能可能超过快排 |
| 希尔排序 | 否 | 是 | 1 | 插入排序的改良版, 改善了插入排序过于局限 | |
| 快速排序 | 否 | 是 | NlogN | lgN | 分治, 运行效率由概率保证 |
| 归并排序 | 是 | 否 | NlogN | N | 自顶向下(递归 分治)和自底向上(从局部到整体) 两种方法 |
| 堆排序 | 否 | 是 | NlogN | 1 | 学完后突然想到了如果在很多的数字中找到最大的多少个数这种问题 |
2.4 优先队列
需要支持两种操作, 删除最大元素和插入元素 - 优先级队列
- 数组实现(无序) - 插入快 删除慢
Insert方法 直接将元素插入尾部, 类似栈的push方法
DelMax方法 使用一个内部循环找出最大的元素和边界元素交换 然后删除边界元素, 删除的时候类似pop方法
- 数组实现(有序) - 插入慢 删除快
Insert方法 中进行排序, 插入新的元素的时候将较大元素向右移动一格位置, 然后插入新的元素
DelMax方法 直接删除右侧元素, 类似栈的pop方法
- 链表表示法
无序序列是解决问题的惰性方法, 仅在必要的时候才会采取行动 找出最大元素
有序序列是解决问题的积极方法, 尽可能的未雨绸缪, 使得找出最大元素高效
二叉堆表示法 - 插入和删除都为线性对数级别
Insert方法 将新元素添加到数组末端, 增加了堆的大小 将新元素上浮到合适的位置
DelMax方法 删除顶部元素 将数组的最后一个元素放到顶部 将其下沉到合适的位置 减小了堆的大小 将
堆
二叉堆: 每个元素都要保证小于等于(大于等于)另外两个特定位置的元素. 其根节点是最小(最大)元素
- 二叉堆的指针表示法
需要使用三个指针, 指向父节点和两个子节点
- 使用数组
完全二叉树可以使用数组表示 不使用数组的0位置元素 从1开始 k的子节点分别在2k和2k+1
堆的有序化
以最大堆为例
- 由下至上的堆有序化
上浮
堆的有序状态因为 某个节点比他的父节点更大 被打破.
需要与父节点交换, 不断向上直到遇到一个更大的父节点 或者到了顶部
- 由上至下的堆有序化
下浮
堆的有序状态因为 某个父节点比 他的两个子节点或其中之一子节点 小 被打破.
将父节点与子节点中较大的一个进行交换直到它的子节点都比它小 获得到了底部
第三章 查找
符号表: 最主要的目的是是将one key和one value联系起来, 是一种存储键值对的数据结构, 支持插入和查找
| 使用的数据结构 | 实现 | 优点 | 缺点 |
|---|---|---|---|
| 链表(顺序查找) | SequentialSearchST | 适用于小型问题 | 对于大型表很慢 |
| 有序数组(二分) | BinarySearchST | 最优的查找和空间需求, 能够进行有序性相关的操作 | 插入操作很慢 |
| 二叉查找树 | BST | 实现简单, 能够进行有序性相关的操作 | 没有性能上界的保证, 链接需要额外的空间 |
| 平衡二叉树 | RedBlackBST | 最优的查找和插入效率, 能够进行有序性相关的操作 | 链接需要额外的空间 |
| 散列表 | SeparateChainHashST LinearProbingHashST | 能够快速的查找和插入常见的数据类型 | 需要计算散列, 无法进行有序性相关操作, 链接和空节点需要额外的空间 |
红黑树
介绍红黑树之前书中先介绍了2-3树先说明2-3树的基本理想操作和优点. 然后说出其缺点(编码实现和维护较复杂), 引出了红黑树
红黑树中的红: 红色链接将两个2-结点连接起来构成一个3-结点, 且这条连接是左斜的两个节点之一是另一个节点的左子节点. 同时不存在一个节点同时有两条红色链接
红黑树中的黑: 普通的结点
将红黑树中的红色链接画平行, 这样所有的空节点到根节点的路径都是相同的
红黑树需要通过左旋转和右旋转以及颜色转换保证插入后不会存在右斜红色链接和同时有两个红色链接的连接