- 第1章 、算法简介
- 1.3
- 第2章 、选择排序
- 2.2 数组
- 2.2.1 链表
- 2.3 选择排序
- 第3章 、 递归
- 3.1 递归
- 3.2 基线条件和递归条件
- 3.3栈(Stack)
- 第4章 、 快速排序
- 4.1 分而治之
大O表示法：指出了算法有多快，算法运行时间的增速，比较操作数。
最糟情况下的运行时间：O(n)
常见大O表示运行时间：
| 运行时间 | 算法 |
|---|---|
| O(n) | 简单查找 |
| O(log n) | 二分查找 |
| O(n * log n) | 速度较快算法 |
| O(n^2) | 速度较慢算法 |
| O(n!) | 速度非常慢算法 |
谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加第2章 、选择排序 2.2 数组
数组在内存中是连续序列，后添加的元素必须紧挨之前的元素内存地址，会出现后续内存地址被占用的情况。 数组的优势是读数据，支持随机访问，写数据不具有优势。 数组元素的索引从0开始。
解决方法：提前声明数组容量
| 方法 | 缺点 |
|---|---|
| 提前声明数组容量 | 用不上的位置会造成内存浪费 |
| 提前声明数组容量 | 可能会出现声明容量依然不足 |
链表中的元素可存储在内存中任意位置，链表中的每一个元素都存储了下一个元素的地址。 链表的插入：将元素放入内存中，并将其地址存储到前一个元素中。 链表的优势在于插入元素，但读取的效率很低，不支持随机访问，读取最后一个元素需要从第一个元素开始读，使用顺序访问。 需要在中间插入元素时，链表是最好的选择，只需要修改前面元素指向的地址。 删除元素时，链表也是最好的选择，也只需要修改前面元素指向的地址，删除操作任何时候都会成功，而插入不一定，会出现内存不足的问题。
数组与链表操作的运行时间比较：
| 操作 | 数组 | 链表 |
|---|---|---|
| 插入 | O(n) | O(1) |
| 读取 | O(1) | O(n) |
| 删除 | O(n) | O(1) |
遍历一个列表，找出最大值，存入一个新的列表中，再遍历剩下的列表，找出第二大值，存入刚才的新列表中，依此类推，直到遍历完所有数据。
| 名称 | 时间复杂度 |
|---|---|
| 选择排序 | O(n^2) |
调用自己的函数 递归只是让解决方案更清晰，并没有性能上的优势。
如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。
3.2 基线条件和递归条件编写递归函数时，必须告诉他递归何时停止。
| 条件 | 作用 |
|---|---|
| 基线条件 | 函数不再调用自己，避免无限循环 |
| 递归条件 | 函数调用自己 |
先进后出 所有函数调用都进入调用栈。 主要操作有压栈(插入)和弹出(删除和读取) 调用栈可能很长，这将占用大量的内存。 调用另一个函数时，当前函数暂停并处于未完成状态，该函数的所有变量的值都还在内存中。第4章 、 快速排序
快速排序使用分而治之的策略，递归式问题解决方法。（divide and conquer, D&C）
4.1 分而治之一种解决问题的思路。
使用D&C解决问题的两个步骤：
- 找出基线条件，这种条件必须尽可能简单。
- 不断将问题分解（或者说缩小规模），直到符合基线条件。
每次递归调用都必须缩小问题的规模。
适用于小块地的最大方块，也是适用于整块地的最大方块。
编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。
