git创建新仓库
小灰的算法之旅
1.算法和数据结构
- 算法是什么？ 算法是一系列程序指令，用来处理特定运算和逻辑问题。
- 什么是数据结构？ 数据结构是数据的组织、管理和存储格式，其使用的目的是为了高效的访问和修改。 数据结构包含数组，链表。以及树，图这种复杂的数据结构。 3.什么是时间复杂度？ T(n) = O(f(n)) 4.什么是空间复杂度？ S(n) = O(f(n))
2.数据结构基础
- 数组VS链表
| VS | 查找 | 更新 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(1) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) | O(1) |
栈和队列
栈是先入后出FILO(First In Last Out) 入栈：PUSH 出栈：POP 可以用来实现递归逻辑，以及面包屑导航（浏览器浏览历史回退）
队列是先入先出FIFO(First In First Out) 队头:Front 队尾：Rear 入队：enquere 出队：dequeue
散列表（哈希表 hash table） 散列表也叫哈希表，是存储Key-Value的集合，对于一个key，散列表可以在接近 O(1)的时间内完成读写操作。散列表通过哈希函数实现key和数组下标的转换，通过开放寻址法和链表法来解决冲突。 哈希函数：通过哈希函数，可以将字符串和其他类型的Key，转换成数组下标index 例如Key=abcd,index= HashCode(“abcd”)%Array.length = 1420036703%8 = 7 hashcode: 区分不同对象的唯一标识，整形变量，通过取模运算获得（java为了优化性能，采用位运算） 解决冲突： 开放寻址法： 链表法：（java采用此方法）【数组+链表的结合】 扩容：HashMap.size >= Capicity × LoadFactor 时扩容 Capicity：当前HashMap长度 LoadFactor：负载因子，默认为0.75f 创建一个新的hashMap，容量为原来两倍并重新散列，JDK 8之后，会把Entry链表转为红黑树这种数据结构。
3.树
树：树是n个节点的有限集，有且仅有一个特定的称为根的节点。当n>=1时，其余节点可以分为m个互不相交的有限集，每一个集合本身又是一个树，并成为根的子树。 二叉树：二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式。 满二叉树：一个树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上 完全二叉树：有一个n节点的二叉树，按照层级顺序编号，则所有的节点编号从1到n,如果这个树所有节点和同样深度的满二叉树的编号从1到n的节点位置相同，则为完全二叉树。
二叉树可以用 1.链式存储结构：data,left,right 2.数组：如果父节点下标是parant,则左孩子节点下标为2 × parent+1,右孩子节点为2 × parent+2，如果孩子节点为child，则父节点下标为(child-1)/2 来表达。
主要作用：查找操作、维持相对顺序
二叉查找树：除满足二叉树的特点外，还需满足下面3个条件 - 如果 左子树不为空，则左子树上所有节点的值均小于根节点的值。 - 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。 - 左、右子树都是二叉查找树。 对于一个节点分布相对均很的二叉查找树来说，搜索节点的时间复杂度就是O(logn)，和树的深度是一样的。
因为二叉查找树要求左子树小于父节点，右子树大于父节点，保证二叉树的有序性，因此二叉查找树还有另外一个名字 二叉排序树（binary sort tree） 二叉树的自平衡有很多种：红黑树、AVL树、树堆等
二叉树的遍历： - 深度优先遍历（1.前序遍历【根，左，右】，2.中序遍历【左，根，右】，3.后续遍历【左，右，根】） - 广度优先遍历（4.层序遍历）
深度优先遍历实现可以用递归，也可以用栈来实现。 广度优先遍历实现可以用队列。
二叉堆：本质上是一种完全二叉树 最大堆：任何一个父节点的值，都大于或等于它左右孩子节点的值。 最小堆：任何一个父节点的值，都小于或等于它左右孩子节点的值。 二叉堆的根节点叫做堆顶。 二叉堆的自我调整：把一个不符合堆性质的完全二叉树，调整为一个堆 - 1.插入节点 - 2.删除节点 - 3.构建二叉堆
优先权队列:二叉堆来实现
4.排序
O(n²)的排序 1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 O(nlogn)的排序 1.快速排序 2.归并排序 3.堆排序 时间复杂度为线性的排序算法 1.计数排序 2.桶排序 3.基数排序
根据稳定性还可划分为：稳定排序和不稳定排序
冒泡排序：把相邻的两个元素比较，当一个元素大于右侧相邻的元素时，交换他们的位置；当一个元素小于等于右侧相邻元素时，位置不变。 快速排序：每一轮挑选一个基准元素(pivot),并让其他比它大的元素移动到数的一边，比它小的元素移动到数列的另一边，从而把数列拆分成两个部分。这种思路叫分治法。 元素的交换又两种实现： 1.双边循环法 2.单边循环法
非递归实现采用栈的形式。
堆排序:
1.把无序数组构建成二叉堆，需要 从小到大排序，则构建最大堆。需要从大到小排序，则构建最小堆。 2.循环删除堆顶元素，替换到二叉堆的末尾，调整堆生产新的堆顶。
参考: 小灰的算法之旅