研一算法导论课程，为了加深自己对算法的理解，将算法导论内容整理于此。
第一部分 基础知识
1. 各种基础
各种定义
算法：通用性、有效性、确定性、有穷性。
数据结构：一种存储和组织数据的方式。
时间复杂度符号：Θ：渐进的给出函数的上界和下界。O：（只有）渐进上界。Ω：（只有）渐进下界。
其他时间复杂度符号：o：非紧的渐进上界，w：非紧的渐进下界。
时间复杂度计算法：代入法，递归树法，主方法。
伪随机数生成器：是一种确定性算法，返回的值统计上随机。
伪代码规则
样例1：
样例2：
2. 分治策略
分治思想
分治法求解问题：分解、解决、合并。其中，主函数负责分解和合并，子函数负责解决。
分治相关算法问题
最大子数组问题
- 问题实例：买股票
- 求解算法：分治法
- 求解思路：
- 函数：findMaximumSubarray主函数，findMaxCrossingSubarray子函数
3. 冒泡排序
4. 插入排序
插入排序算法：
图解：
5. 归并排序
时间复杂度 O(n log n)
归并排序算法：主函数：mergeSort，子函数：merge
图解：
第二部分 排序和顺序统计量
1. 堆排序
堆排序相关内容
时间： O(n log n)
空间：有空间原址性，常数空间复杂度。
堆：近似的完全二叉树，所以又叫二叉堆。
最大堆：除了根节点，其他节点都不大于父节点。最小堆反之。也就是最大最小是指根的性质是最大还是最小。最小堆常用于优先队列。
常用函数：维护最大堆 maxHeapify，构建最大堆 buildMaxHeap，堆排序 heapSort，构建优先队列 maxHeapInsert、heapExtractMax、heapIncreaseKey、heapMaximum。
maxHeapify 算法、图例及时间复杂度 O(h)：
buildMaxHeap 算法、图例、时间复杂度 O(n)：
heapSort 算法、图例、时间复杂度 O(n log n)：
优先队列相关内容
优先队列：
应用：操作系统作业调度，根据优先级排列作业调度顺序。
2. 快速排序
快速排序也采用了分治法思想。
时间：期望为 O(n log n)，且常数项非常小，一般比堆排序还快。
快速排序算法：主函数：quickSort，子函数：partition
图解：
可以进行随机化改进子函数 partition：
3. 线性时间排序
比较排序和线性时间排序
比较排序：元素次序依赖比较的排序。前面提到的排序都是线性时间排序。比较排序的时间下界为 Ω(n log n)。
线性时间排序：包括 计数排序、基数排序和桶排序，它们依赖计算而不是比较。它们的时间下界是 Ω(n)。
计数排序
计数排序用一个数组存储每种数的数量，最后排多少位直接计数就能算出。
计数排序算法：
图解：
基数排序
基数排序从低位到高位，按照指定位排序。这也要求每次的排序都必须是稳定的排序算法。
基数排序算法：
图解：
桶排序
桶排序将区间划分为
Comments | NOTHING