数组
核心：连续的内存空间。
已知数组的起始地址和每个元素的所占字节，求任意元素的地址。
查找：O(1)，内存连续
插入：O(n), 移动元素
删除：O(n), 移动元素
适用场景：适合于查询占大多数， 插入删除比较少的情况。
int[] array = new int[]{1,2,3};链表
核心：非连续的内存空间
在当前元素的内部，记录下一元素的指针（引用）。
class LinkedList{
private int val;
public LinkedList next;
// 默认存在，不写也有
public LinkedList() {}
// 有参数的构造函数，目的就是为了初始化类的成员变量
public LinkedList(int _val) {
this.val = _val;
}
public void setVal(int _val){
this.val = _val;
}
}
LinkedList list = new LinkedList(5);
LinkedList node = new LinkedList(6);
list.next = node;
链表节点结构分为两部分，一部分为元素域，记录该节点的值；另一部分为指针域，记录下一节点的指针（地址）。
查找：要找链表中第3个元素，怎么找？O(n)
删除：假设我已经找到这个元素了，只需要更改下一元素的指针（地址），O(1)
插入：O(1)
栈
栈是先进后出。插入和删除只能在栈顶进行。
栈的应用：
凡是涉及到深度优先搜索（DepthFirstSearch）的时候，就使用栈。
括号的匹配。
数组的反转。
链表反转。队列
队列是先进先出，插入在队尾进行，而删除在队首进行。
队列的应用：
凡是涉及到广度优先搜索（BreadthFirstSearch）的时候，就使用队列。
二叉的层次遍历
优先队列（堆）树，二叉树、二叉搜索树、B-树与B+树
5.1. 基础概念
5.2. 三种遍历：
1）先(前)序遍历 根结点-左子树-右子树
若二叉树为空，则空操作，否则先访问根节点，再先序遍历左子树，最后先序遍历右子树。
/**
* 前序遍历的递归实现
* 若二叉树为空，则空操作，否则先访问根节点，再先序遍历左子树，最后先序遍历右子树。
* @param root
* @return
*/
public void preorderTraversalRecursive(TreeNode root) {
if (root == null) {
return;
}
// 先访问根结点
System.out.println(root.val);
// 先序访问左子树
preorderTraversalRecursive(root.left);
// 再先序访问右子树
preorderTraversalRecursive(root.right);
}
- 中序遍历 左子树-根结点-右子树
若二叉树为空，则空操作；否则先中序遍历左子树，再访问根结点，最后中序遍历右子树。
/**
* 中序遍历的递归实现
* 若二叉树为空，则空操作，否则先中序遍历左子树，再访问根节点，最后中序遍历右子树。
* @param root
* @return
*/
public void inorderTraversalRecursive(TreeNode root) {
if (root == null) {
return;
}
// 中序遍历左子树
inorderTraversalRecursive(root.left);
// 访问根节点
System.out.println(root.val);
// 中序遍历右子树
inorderTraversalRecursive(root.right);
}
- 后序遍历 左子树- 右子树-根结点
若二叉树为空，则空操作；否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。
/**
* 后序遍历的递归实现
* 若二叉树为空，则空操作；否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。
* @param root
* @return
*/
public void postorderTraversalRecursive(TreeNode root) {
if (root == null) {
return;
}
// 后序遍历左子树
postorderTraversalRecursive(root.left);
// 后序遍历右子树
postorderTraversalRecursive(root.right);
// 访问根节点
System.out.println(root.val);
}
5.3. 二叉查找树，也叫二叉搜索树
左子树的节点值 < 根结点 < 右子树的节点值 ，所以，中序输出即有序输出。
5.4. 平衡二叉查找树-》AVL树-》红黑树
红黑树是平衡二叉树的一种，它保证在最坏情况下基本动态集合操作的时间复杂度为O(log n)。红黑树和平衡二叉树区别如下：(1) 红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。(2) 平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知
5.5. B-树 与 B+树的区别
B-树 -》 MyISM
B+树 -》 InnoDB
- B-树数据不仅存储在叶子结点上，每个节点都存储数据。B+树，非叶子节点只存主键和下一层节点的指针，不存储数据；叶子节点存储数据，即指向数据记录的指针。
- B+树为所有叶子结点增加了一个链指针
B树和B+树的区别：
1.（主键索引）B树的每个节点中存储指向主键记录的指针（地址），而B+树只有在叶子节点才会存储主键指向数据记录的指针，其他节点只存储主键；
（非主键索引）B树的每个节点存储索引的指针，B+树只有叶子节点才会存储索引的指针，其他节点只存储索引值对应的主键 ID；
2.B+树的叶子节点是有序且用链表连接起来的，读取数据的时候，根据磁盘的预加载逻辑，会把相邻节点的数据加载进内存，这样会降低读物磁盘的io复杂度；而B树的叶子节点没有链表相连；
联合索引（name, age）;
SELECT * FROM student where name = 'zhangsan'; ✅
SELECT * FROM student where name = 'zhangsan' AND age = 19;✅
SELECT * FROM student where age = 19; X
SELECT * FROM student where age = 19 AND name = 'zhangsan'; X
图
定义：图通常用来表示和存储具有“多对多”关系的数据，是数据结构中非常重要的一种结构。
组成：节点、边
2.1. 邻接矩阵：排序
1）快速排序：
- 算法思路：
使用 i , j 两个指针（数组下标）分别指向待排数组nums的左、右下标（left,right），将待排数组第一个元素作为枢纽元素(记为pivot)。
在i < j的前提条件下，进入大循环：
1）如果nums[j] >= pivot，则j--，依次往前遍历，直到不满足条件（即nums[j] < pivot），则 交换nums[i]和nums[j];
2）如果nums[i] <= pivot，则i++，依次往后遍历，直到不满足条件（即nums[j] > pivot），则 交换nums[i]和nums[j];
当i = j时，代表此轮排序已完成，结果为：小于pivot的元素在pivot的左边，大于pivot的元素在pivot的右边；
接下来，我们再递归的快排处理pivot左边和pivot右边部分的元素即可。即nums[left, i - 1]和nums[i + 1, right]。
递归结束后，快速排序结束。 - 时间复杂度：最好情况下O(nlogn); 最坏情况下：O(n^2)，正好倒序的情况下
- 空间复杂度：O(1)
- 不稳定的排序算法
- 代码实现：
public int[] sort(int[] nums) {
int i = 0;
int j = nums.length - 1;
partition(nums, i, j);
return nums;
}
private void partition(int[] nums, int left, int right) {
if (left > right) {
return;
}
int i = left;
int j = right;
int pivot = nums[i];
while (i < j) {
while (i < j && nums[j] >= pivot) {
j--;
}
if (i < j) {
nums[i] = nums[j];
}
while (i < j && nums[i] <= pivot) {
i++;
}
if (i < j) {
nums[j] = nums[i];
}
}
nums[i] = pivot;
partition(nums, left, i - 1);
partition(nums, i + 1, right);
}
2）冒泡排序
记录数组最左边和最右边的元素下标为i和j，从i往j遍历，从i开始将数组相邻元素两两比较，如果左边元素小于右边元素，则交换两者位置，直到数组最右边元素为整个数组最大元素，此时 j--，直到i<j为止，退出循环；
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定的排序算法
public int[] sort(int[] nums) {
boolean swapped = false;
for (int j = nums.length - 1; j > 0; j--) {
for (int i = 0; i < j; i++) {
if (nums[i] > nums[i + 1]) {
swapped = true;
Swapper.swap(nums, i, i + 1);
}
}
if (!swapped) {
break;
}
}
return nums;
}
3）插入排序
从数组第二个元素开始，依次与左边元素（保证左边元素是有序的）比较，在左边已经排序好的部分找到一个合适的位置j进行插入：该合适位置满足nums[j] <= val 并且 nums[j + 1] > val;
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定的排序算法
public int[] sort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int val = nums[i];
int j = i;
for (; j > 0; j--) {
if (nums[j - 1] > val) {
nums[j] = nums[j - 1];
} else {
break;
}
}
nums[j] = val;
}
return nums;
}
}
进程、线程和协程
进程是操作系统分配资源的最小单位
线程是操作系统调度的最小单位；
一个进程可以包含多个线程；
协程是线程的线程；协程运行用户态，几乎没有上下文切换的代价。Go语言对此支持较好
- 死锁的四个条件：
1）互斥。即一个资源同一时刻只能被一个线程所占有。
2）占有且请求。线程总是占有一个资源后，再去请求其他的资源。
3）不可抢占。资源除非被线程自己释放，否则不可被其他线程抢占。
4）环路等待。A请求B，B请求C，C请求A，资源请求形成一个环路。
