Data_structure Algorithm and Design_pattern¶
Include all data structure.
Include 10 sort algorithm and 7 search algorithm.
Include 6 principle and 23 design patterns.
data structure¶
数据结构
String/字符串¶
- KMP算法
- BM模式匹配算法
- BF算法
Vector/向量¶
顺序线性表
Linked List/链表¶
- 双向链表/Double Linked Lists
- 静态链表/Static List
- 对称矩阵/Symmetric Matrix
- 稀疏矩阵/Sparse Matrix
Stack/栈¶
- 广义表/Generalized List
- 双端队列/Deque
Queue/队列¶
- 链表实现
- 循环数组实现
- 双端队列
- 优先队列
- 循环队列
Heap/堆¶
- 数组实现的堆
- 树实现的堆
Tree/树¶
- 二叉树/Binary Tree
- 并查集/Union-Find
- Huffman数
Graph/图¶
fibonacci sequence¶
斐波那契数列,也叫黄金分割数列:
0, 1, 1, 2, 3, 5, 8, 13, ...
seq[0] = 0
seq[1] = 1
seq[n] = seq[n-1] + seq[n-2] (n>=2)
Algorithm¶
对数¶
loga^b = x => a^x = b
loga^(mn) = loga^m + loga^n
loga^(m/n) = loga^m - loga^n
loga^(M^n) = nloga^M
loga^b = logc^b / logc^a
ln e为底 lg 10为底 log 任意底
时间复杂度¶
渐进时间复杂度，表示数据规模和运算时间之间的关系。
常见时间复杂度从小到大排列: 1. O(1) 常数阶 2. O(logn) 对数阶 3. O(n) 线性阶 4. O(nlogn) 线性对数阶 5. O(n^2) 平方阶 6. O(n^3) 立方阶 7. O(2^n) 指数阶 8. O(n!) 阶乘阶 9. O(n^n) k次方阶
Comparison sort¶
七大比较排序算法
bubble sort/冒泡排序¶
始终是未排序的两个相邻值比较.
用第0个和第1个比较，如果第0个大就交换位置…用倒数第二个和最后一个比较，如果倒数第二个大就交换位置。 第一轮就是从前往后相邻的比较，最大的数就在最后一个位置。 用第0个和第一个比较，如果第0个大就交换位置…用倒数第三个和倒数第二个比较，如果倒数第三个大就交换位置。 第二轮就是从前到倒数第二个相邻的比较，第二大的就在倒数第二位置。 依次类推 …
i表示比较几轮（总共比较len-1轮），j表示每次多少个相邻的数比较（每轮比较len-1-i次）。
时间复杂度
平均O(n<sup>2</sup>) 最好O(n) 最差O(n<sup>2</sup>)
空间复杂度
平均O(1)
稳定性
稳定
selection sort/选择排序¶
始终是假设的最值和后面未排序的值依次比较。
第一轮，默认下标为0的位置是最值,然后用这个位置的值和后面的依次比较,如果发现真的最值,就把这个值所在的下标设置新的最值下标. 如果一轮比较完成，最小值下标不是0，就交换位置，将最小值放到第一。 以此类推。 …
i表示比较几轮(len-1), j表示每轮比较的次数(len - (i+1)).
时间复杂度
平均O(n<sup>2</sup>) 最好O(n<sup>2</sup>) 最差O(n<sup>2</sup>)
空间复杂度
O(1)
稳定性
不稳定
insertion sort/插入排序¶
插入排序，从第二个元素开始，每次和前面的序列比较，和前面的序列从后往前比较，找到合适的插入位置。
时间复杂度
平均 O(n<sup>2</sup>) 最好 O(n) 最差 O(n<sup>2</sup>)
空间复杂度
O(1)
稳定性
稳定
shell sort/希尔排序¶
希尔排序是基于插入排序的，通过逐步缩小插入排序的增量实现。
可以用序列长度的一半作为gap。
基于经验的一组序列：
Marcin Ciura’s gap sequence: gaps = [701, 301, 132, 57, 23, 10, 4, 1]
例如gap=10, 就是0和10比较，1和11比较； gap=4 就是0和4比较，1和5比较。
时间复杂度
平均 O(nlog(n)) ~ O(n<sup>2</sup>) 最好 O(n<sup>1.3</sup>) 最差 O(n<sup>2</sup>)
空间复杂度
O(1)
稳定性
不稳定
quick sort/快速排序¶
快速排序是冒泡排序的升级版,是目前速度最快的排序,采用分治策略。
从数列中取一个数作为基准数，将比这个数大的数放到右边，小于等于的放到左边。 再对左边和右边的做上述同样的操作，直到各个区间只有一个数。
时间复杂度
平均 O(nlog(n)) 最好 O(nlog(n)) 最差 O(n<sup>2</sup>)
空间复杂度
O(log(n)) ~ O(n)
稳定性
不稳定
merge sort/归并排序¶
时间复杂度
平均 O(nlog(n)) 最好 O(nlog(n)) 最差 O(nlog(n))
空间复杂度
O(n)
稳定性
稳定
Non comparison sort¶
基数排序,计数排序,桶排序三种排序都是非比较排序.
radix sort/基数排序¶
counting sort/计数排序¶
bucket sort/桶排序¶
search algorithm¶
七大查找算法
binary search/二分查找¶
二分查找又叫折半查找.只能用于有序序列。
设置三个下标，min=0, max=array.length - 1, mid = (min+max)/2。 然后用要查找的关键值key和mid下标的元素比较。 如果key比array[mid]大，那么将数组一分为二，min变为mid+1,mid重新计算。 如果key比array[mid]小，那么数组一分为二，max变为mid-1,mid重新计算。 如果key==array[mid]那么找到了。 如果min>=max那么没有找到。 依次类推，每次将数组一分为二。
- 时间复杂度
- 空间复杂度
interpolation search/插值查找¶
插值查找是二分查找的优化版，同样只能用于有序序列。
核心是计算公式: (key-array[min]) / (array[max] - array[min])
mid = min + (max-min) * (key-array[min]) / (array[max]-array[min])
- 时间复杂度
- 空间复杂度
tb search/树表查找¶
block search/分块查找¶
hash search/哈希查找¶
design pattern principle¶
设计模式的5个原则: S.O.L.I.D
single responsibility principle¶
单一职责原则
open closed principle¶
开闭原则
liskov substitution principle¶
里氏替换原则
interface segregation principle¶
接口隔离原则
dependency inversion principle¶
依赖倒置原则
creational patterns¶
５个创建型模式
Factory pattern¶
简单工厂模式: 它提供了一种将实例化逻辑委托给子类的方法。
当类中有一些通用处理但所需的子类在运行时动态决定时很有用。或者换句话说，当客户不知道它可能需要什么确切的子类时。
Abstract Factory pattern¶
抽象工厂模式: 工厂的工厂；一个工厂，它将单独但相关/依赖的工厂组合在一起，而不指定它们的具体类。
当存在相互关联的依赖关系并涉及不那么简单的创建逻辑时.
Builder pattern¶
建造者模式
允许您创建不同风格的对象，同时避免构造函数污染。当一个对象可能有多种风格时很有用。或者当创建一个对象涉及很多步骤时。
当一个对象可以有几种类型时，为了避免构造函数伸缩。与工厂模式的关键区别在于;当创建是一个一步过程时使用工厂模式，而当创建是一个多步骤过程时使用构建器模式。
Prototype pattern¶
原型模式, 通过克隆基于现有对象创建对象。简而言之，它允许您创建现有对象的副本并根据需要对其进行修改，而无需经历从头开始创建对象并进行设置的麻烦。
当需要一个与现有对象相似的对象时，或者当创建与克隆相比代价高昂时。
behavioral patterns¶
11个行为型模式
structural patterns¶
7个结构型模式
