数据结构与算法思维导图模板_ProcessOn思维导图、流程图

复杂度分析

空间复杂度

时间复杂度

最好

最坏

平均

均摊

线性表(增、删、改、查) ‌线性结构：数据元素之间是一对一的关系。

栈

顺序栈

链式栈

数组

数组（Array）是一种线性表数据结构。 ‌它用一组连续的内存空间，来存储一组 ‌具有相同类型的数据。

插入：<div>若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。</div><div>最好情况时间复杂度 O(1)</div>

最坏情况复杂度为O(n)

平均负责度为O(n)

1）插入：从最好O(1) 最坏O(n) 平均O(n)<div>2）插入：数组若无序，插入新的元素时，</div><div>可以将第K个位置元素移动到数组末尾，把</div><div>心的元素，插入到第k个位置，此处复杂度为O(1)。</div><div>3）删除：从最好O(1) 最坏O(n) 平均O(n)</div><div>4）多次删除集中在一起，提高删除效率</div>

 连续的内存空间和相同类型的数据(随机访问的前提)。

优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低。

对内存空间要求高，需要一块连续的内存空间

链表

单链表(增、删、改、查)

每个节点只包含一个指针，即后继指针。

单链表有两个特殊的节点，即首节点和尾节点。 ‌为什么特殊？用首节点地址表示整条链表，尾节点 ‌的后继指针指向空地址null。

性能特点：插入和删除节点的时间复杂度为O（1）， ‌查找的时间复杂度为O(n)。

双向链表(增、删、改、查)

节点除了存储数据外，还有两个指针分别指向前一个节点地址 ‌（前驱指针prev）和下一个节点地址（后继指针next）。

首节点的前驱指针prev和尾节点的后继指针均指向空地址。

性能特点：<div>和单链表相比，存储相同的数据，需要消耗更多的存储空间。</div>

循环链表(增、删、改、查)

除了尾节点的后继指针指向首节点的地址外均与单链表一致。

适用于存储有循环特点的数据，比如约瑟夫问题。

队列(增、删、改、查)

队列是一种受限的线性表数据结构,只支持两个操作:入队enqueue(),放一个数据到队列尾部; ‌出队dequeue0),从队列头部取一个元素。

队列跟栈一样,也是一种抽象的数据结构。

具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

队列可以用数组来实现,也可以用链表来实现。<div> </div><div>用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。</div>

常见概念

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的逻辑结构：数据对象中数据元素之间的相互关系，分为线性结构、树形结构、图形结构以及集合结构。

数据结构的物理结构：数据的逻辑结构在计算机中的存储形式，分为顺序存储和链式存储（不连续存储）。

算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法五个基本特性：输入、输出、有穷性、确定性和可行性。

树形结构

数据元素之间存在一对多的层次关系

度：结点拥有的子树数

树的度：树内各结点的度的最大值

叶结点/终端结点：度为0的结点

树的深度/高度：树中结点的最大层次

图 ‌图(Graph)是由顶点和连接顶点的边构成的离散结构。

无向图

有向图

图的存储

邻接矩阵*

图的邻接矩阵的存储方式是用两个数组来实现的，一个一维数组存储顶点信息， ‌一个二维数组存储线（无向图）或弧（有向图）的信息。

邻接表*

邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。

算法

基本算法思想

贪心算法

分治算法

动态规划

回溯算法

枚举算法

分支界限算法

概率算法

排序

O(n*2)

冒泡排序

// 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         for (int i = 1; i < arr.length; i++) {             // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。             boolean flag = true;             for (int j = 0; j < arr.length - i; j++) {                 if (arr[j] > arr[j + 1]) {                     int tmp = arr[j];                     arr[j] = arr[j + 1];                     arr[j + 1] = tmp;                     flag = false;                 }             }             if (flag) {                 break;             }

插入排序

// 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的         for (int i = 1; i < arr.length; i++) {             // 记录要插入的数据             int tmp = arr[i];             // 从已经排序的序列最右边的开始比较，找到比其小的数             int j = i;             while (j > 0 && tmp < arr[j - 1]) {                 arr[j] = arr[j - 1];                 j--;             }             // 存在比其小的数，插入             if (j != i) {                 arr[j] = tmp;             }         }

选择排序

int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         // 总共要经过 N-1 轮比较         for (int i = 0; i < arr.length - 1; i++) {             int min = i;             // 每轮需要比较的次数 N-i             for (int j = i + 1; j < arr.length; j++) {                 if (arr[j] < arr[min]) {                     // 记录目前能找到的最小值元素的下标                     min = j;                 }             }             // 将找到的最小值和i位置所在的值进行交换             if (i != min) {                 int tmp = arr[i];                 arr[i] = arr[min];                 arr[min] = tmp;             }         }

希尔排序

public class ShellSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         int gap = 1;         while (gap < arr.length/3) {             gap = gap * 3 + 1;         }         while (gap > 0) {             for (int i = gap; i < arr.length; i++) {                 int tmp = arr[i];                 int j = i - gap;                 while (j >= 0 && arr[j] > tmp) {                     arr[j + gap] = arr[j];                     j -= gap;                 }                 arr[j + gap] = tmp;             }             gap = (int) Math.floor(gap / 3);         }         return arr;     } }

O(nlogn)

归并排序

public class MergeSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         if (arr.length < 2) {             return arr;         }         int middle = (int) Math.floor(arr.length / 2);         int[] left = Arrays.copyOfRange(arr, 0, middle);         int[] right = Arrays.copyOfRange(arr, middle, arr.length);         return merge(sort(left), sort(right));     }     protected int[] merge(int[] left, int[] right) {         int[] result = new int[left.length + right.length];         int i = 0;         while (left.length > 0 && right.length > 0) {             if (left[0] <= right[0]) {                 result[i++] = left[0];                 left = Arrays.copyOfRange(left, 1, left.length);             } else {                 result[i++] = right[0];                 right = Arrays.copyOfRange(right, 1, right.length);             }         }         while (left.length > 0) {             result[i++] = left[0];             left = Arrays.copyOfRange(left, 1, left.length);         }         while (right.length > 0) {             result[i++] = right[0];             right = Arrays.copyOfRange(right, 1, right.length);         }         return result;     } }

快速排序

public class QuickSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         return quickSort(arr, 0, arr.length - 1);     }     private int[] quickSort(int[] arr, int left, int right) {         if (left < right) {             int partitionIndex = partition(arr, left, right);             quickSort(arr, left, partitionIndex - 1);             quickSort(arr, partitionIndex + 1, right);         }         return arr;     }     private int partition(int[] arr, int left, int right) {         // 设定基准值（pivot）         int pivot = left;         int index = pivot + 1;         for (int i = index; i <= right; i++) {             if (arr[i] < arr[pivot]) {                 swap(arr, i, index);                 index++;             }         }         swap(arr, pivot, index - 1);         return index - 1;     }     private void swap(int[] arr, int i, int j) {         int temp = arr[i];         arr[i] = arr[j];         arr[j] = temp;     } }

堆排序

public class HeapSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         int len = arr.length;         buildMaxHeap(arr, len);         for (int i = len - 1; i > 0; i--) {             swap(arr, 0, i);             len--;             heapify(arr, 0, len);         }         return arr;     }     private void buildMaxHeap(int[] arr, int len) {         for (int i = (int) Math.floor(len / 2); i >= 0; i--) {             heapify(arr, i, len);         }     }     private void heapify(int[] arr, int i, int len) {         int left = 2 * i + 1;         int right = 2 * i + 2;         int largest = i;         if (left < len && arr[left] > arr[largest]) {             largest = left;         }         if (right < len && arr[right] > arr[largest]) {             largest = right;         }         if (largest != i) {             swap(arr, i, largest);             heapify(arr, largest, len);         }     }     private void swap(int[] arr, int i, int j) {         int temp = arr[i];         arr[i] = arr[j];         arr[j] = temp;     } }

O(n)

计数排序

public class CountingSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         int maxValue = getMaxValue(arr);         return countingSort(arr, maxValue);     }     private int[] countingSort(int[] arr, int maxValue) {         int bucketLen = maxValue + 1;         int[] bucket = new int[bucketLen];         for (int value : arr) {             bucket[value]++;         }         int sortedIndex = 0;         for (int j = 0; j < bucketLen; j++) {             while (bucket[j] > 0) {                 arr[sortedIndex++] = j;                 bucket[j]--;             }         }         return arr;     }     private int getMaxValue(int[] arr) {         int maxValue = arr[0];         for (int value : arr) {             if (maxValue < value) {                 maxValue = value;             }         }         return maxValue;     } }

基数排序

public class BucketSort implements IArraySort {     private static final InsertSort insertSort = new InsertSort();     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         return bucketSort(arr, 5);     }     private int[] bucketSort(int[] arr, int bucketSize) throws Exception {         if (arr.length == 0) {             return arr;         }         int minValue = arr[0];         int maxValue = arr[0];         for (int value : arr) {             if (value < minValue) {                 minValue = value;             } else if (value > maxValue) {                 maxValue = value;             }         }         int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;         int[][] buckets = new int[bucketCount][0];         // 利用映射函数将数据分配到各个桶中         for (int i = 0; i < arr.length; i++) {             int index = (int) Math.floor((arr[i] - minValue) / bucketSize);             buckets[index] = arrAppend(buckets[index], arr[i]);         }         int arrIndex = 0;         for (int[] bucket : buckets) {             if (bucket.length <= 0) {                 continue;             }             // 对每个桶进行排序，这里使用了插入排序             bucket = insertSort.sort(bucket);             for (int value : bucket) {                 arr[arrIndex++] = value;             }         }         return arr;     }     /**      * 自动扩容，并保存数据      *      * @param arr      * @param value      */     private int[] arrAppend(int[] arr, int value) {         arr = Arrays.copyOf(arr, arr.length + 1);         arr[arr.length - 1] = value;         return arr;     } }

桶排序

/**  * 基数排序  * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9  */ public class RadixSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         int maxDigit = getMaxDigit(arr);         return radixSort(arr, maxDigit);     }     /**      * 获取最高位数      */     private int getMaxDigit(int[] arr) {         int maxValue = getMaxValue(arr);         return getNumLenght(maxValue);     }     private int getMaxValue(int[] arr) {         int maxValue = arr[0];         for (int value : arr) {             if (maxValue < value) {                 maxValue = value;             }         }         return maxValue;     }     protected int getNumLenght(long num) {         if (num == 0) {             return 1;         }         int lenght = 0;         for (long temp = num; temp != 0; temp /= 10) {             lenght++;         }         return lenght;     }     private int[] radixSort(int[] arr, int maxDigit) {         int mod = 10;         int dev = 1;         for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {             // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)             int[][] counter = new int[mod * 2][0];             for (int j = 0; j < arr.length; j++) {                 int bucket = ((arr[j] % mod) / dev) + mod;                 counter[bucket] = arrayAppend(counter[bucket], arr[j]);             }             int pos = 0;             for (int[] bucket : counter) {                 for (int value : bucket) {                     arr[pos++] = value;                 }             }         }         return arr;     }     /**      * 自动扩容，并保存数据      *      * @param arr      * @param value      */     private int[] arrayAppend(int[] arr, int value) {         arr = Arrays.copyOf(arr, arr.length + 1);         arr[arr.length - 1] = value;         return arr;     } }

搜索

深度优先搜索

广度优先搜索

A*启发式搜索

最小生成树

普利姆(Prim)算法

克鲁斯卡尔(Kruskal)算法

最短路径

迪杰斯特拉算法

弗洛伊德算法

拓扑排序

关键路径

查找

顺序表查找

有序表查找

线性表查找

树形结构查找

B- 树

B 树也属于一种自平衡树。内部通过分裂机制，能够保持数据的有序。它的单个节点中可以保存 2~4 个信息。单个节点内部有序，节点之间信息的间隔，可以作为划分下面部分的依据。

B+ 树

B+树就是为了解决上面抛出的两个问题而设计的。与 B 树相同的是，B+树的节点中也包含了多个信息。但相比于 B 树，B+树做了一些改动：非叶子节点中仅保留数据之间的相对关系，而所有的真实信息均包含在叶子节点中。这样的话，相对关系信息就可以放到内存中，而将所有节点信息（可以认为量较大）保留在磁盘中

B* 树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3 （代替B+树的1/2）； B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据 复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父 结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针； B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分 数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字 （因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之 间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针； 所以，B*树分配新结点的概率比B+树要低，空间使用率更高

BST 搜索二叉树

通过在建树的时候，将大于 root 的值放到右边、小于 root 的值放到左边，即可在查询的时候，减少比较次数，实现加速查询

AVL 平衡二叉树

AVL 树通过在插入过程中的旋转逻辑，使得树的自身高度差严格控制在 1 之内，从而解决了退化成 list 的问题。但是，频繁的旋转增加了树构建的成本

BRT (red black tree) 红黑树

为了降低树构建时的成本，红黑树诞生了。红黑树通过将节点设定成 Red or Black，和同一条边中 Black 节点的数量相同等约束条件，在保证了树基本平衡的情况下，优化了自旋转流程

二叉树

是N（N>=0）个结点的有限集合，该集合或为空集（空二叉树）， ‌或者由一个根结点和两颗互不相交的、分别称为根结点的左子树 ‌和右子树的二叉树组成。

满二叉树

所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号i（1<= i <= n）的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同，则这棵二叉树称为完全二叉树

huffman tree 哈夫曼树

哈夫曼树，又被称为最优二叉树，属于带权值二叉树的一种。它的真实节点全部分布在叶子节点中，是各种可能的组合中 WPL 值最小的形式。组合形式可能不唯一，但 WPL 值一定为最小。WPL（Weighted Path Length），也就是带权路径长度，说简单一些就是【节点到根节点的路径长度 * 该节点的权值】。说白了就是权值越大的节点，离根节点越近就对了

散列表查找

二分查找

插值查找

斐波那契查找

哈希查找

字符串匹配

朴素

KMP

Robin-Karp

Boyer-Moore

AC自动机

trie(前缀树和压缩前缀树)

后缀树