数据结构与算法
2026-04-02 18:24:39 0 举报AI智能生成
算法
算法
模版推荐
作者其他创作
大纲/内容
复杂度分析
空间复杂度
时间复杂度
最好
最坏
平均
均摊
线性表(增、删、改、查)<br>线性结构:数据元素之间是一对一的关系。
栈
顺序栈
链式栈
数组
数组(Array)是一种线性表数据结构。<br>它用一组连续的内存空间,来存储一组<br>具有相同类型的数据。
插入:<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>
连续的内存空间和相同类型的数据(随机访问的前提)。
优点:两限制使得具有随机访问的特性缺点:删除,插入数据效率低。
对内存空间要求高,需要一块连续的内存空间
链表
单链表(增、删、改、查)
每个节点只包含一个指针,即后继指针。
单链表有两个特殊的节点,即首节点和尾节点。<br>为什么特殊?用首节点地址表示整条链表,尾节点<br>的后继指针指向空地址null。
性能特点:插入和删除节点的时间复杂度为O(1),<br>查找的时间复杂度为O(n)。
双向链表(增、删、改、查)
节点除了存储数据外,还有两个指针分别指向前一个节点地址<br>(前驱指针prev)和下一个节点地址(后继指针next)。
首节点的前驱指针prev和尾节点的后继指针均指向空地址。
性能特点:<div>和单链表相比,存储相同的数据,需要消耗更多的存储空间。</div>
循环链表(增、删、改、查)
除了尾节点的后继指针指向首节点的地址外均与单链表一致。
适用于存储有循环特点的数据,比如约瑟夫问题。
队列(增、删、改、查)
队列是一种受限的线性表数据结构,只支持两个操作:入队enqueue(),放一个数据到队列尾部;<br>出队dequeue0),从队列头部取一个元素。
队列跟栈一样,也是一种抽象的数据结构。
具有先进先出的特性,支持在队尾插入元素,在队头删除元素。
队列可以用数组来实现,也可以用链表来实现。<div><br></div><div>用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。</div>
常见概念
数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
数据元素:是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的逻辑结构:数据对象中数据元素之间的相互关系,分为线性结构、树形结构、图形结构以及集合结构。
数据结构的物理结构:数据的逻辑结构在计算机中的存储形式,分为顺序存储和链式存储(不连续存储)。
算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
算法五个基本特性:输入、输出、有穷性、确定性和可行性。
树形结构
数据元素之间存在一对多的层次关系
度:结点拥有的子树数
树的度:树内各结点的度的最大值
叶结点/终端结点:度为0的结点
树的深度/高度:树中结点的最大层次
图<br>图(Graph)是由顶点和连接顶点的边构成的离散结构。
无向图
有向图
图的存储
邻接矩阵*
图的邻接矩阵的存储方式是用两个数组来实现的,一个一维数组存储顶点信息,<br>一个二维数组存储线(无向图)或弧(有向图)的信息。
邻接表*
邻接表存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。
算法
基本算法思想
贪心算法
分治算法
动态规划
回溯算法
枚举算法
分支界限算法
概率算法
排序
O(n*2)
冒泡排序
// 对 arr 进行拷贝,不改变参数内容<br> int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);<br><br> for (int i = 1; i < arr.length; i++) {<br> // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。<br> boolean flag = true;<br><br> for (int j = 0; j < arr.length - i; j++) {<br> if (arr[j] > arr[j + 1]) {<br> int tmp = arr[j];<br> arr[j] = arr[j + 1];<br> arr[j + 1] = tmp;<br><br> flag = false;<br> }<br> }<br><br> if (flag) {<br> break;<br> }
插入排序
// 对 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 {<br><br> @Override<br> public int[] sort(int[] sourceArray) throws Exception {<br> // 对 arr 进行拷贝,不改变参数内容<br> int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);<br><br> int len = arr.length;<br><br> buildMaxHeap(arr, len);<br><br> for (int i = len - 1; i > 0; i--) {<br> swap(arr, 0, i);<br> len--;<br> heapify(arr, 0, len);<br> }<br> return arr;<br> }<br><br> private void buildMaxHeap(int[] arr, int len) {<br> for (int i = (int) Math.floor(len / 2); i >= 0; i--) {<br> heapify(arr, i, len);<br> }<br> }<br><br> private void heapify(int[] arr, int i, int len) {<br> int left = 2 * i + 1;<br> int right = 2 * i + 2;<br> int largest = i;<br><br> if (left < len && arr[left] > arr[largest]) {<br> largest = left;<br> }<br><br> if (right < len && arr[right] > arr[largest]) {<br> largest = right;<br> }<br><br> if (largest != i) {<br> swap(arr, i, largest);<br> heapify(arr, largest, len);<br> }<br> }<br><br> private void swap(int[] arr, int i, int j) {<br> int temp = arr[i];<br> arr[i] = arr[j];<br> arr[j] = temp;<br> }<br><br>}
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 个信息。单个节点内部有序,节点之间信息的间隔,可以作为划分下面部分的依据。<br>
B+ 树
B+树就是为了解决上面抛出的两个问题而设计的。与 B 树相同的是,B+树的节点中也包含了多个信息。但相比于 B 树,B+树做了一些改动:非叶子节点中仅保留数据之间的相对关系,而所有的真实信息均包含在叶子节点中。这样的话,相对关系信息就可以放到内存中,而将所有节点信息(可以认为量较大)保留在磁盘中<br>
B* 树
是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3<br>(代替B+树的1/2);<br><br>B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据<br><br>复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父<br><br>结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;<br><br>B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分<br><br>数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字<br><br>(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之<br><br>间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;<br><br>所以,B*树分配新结点的概率比B+树要低,空间使用率更高<br>
BST 搜索二叉树
通过在建树的时候,将大于 root 的值放到右边、小于 root 的值放到左边,即可在查询的时候,减少比较次数,实现加速查询
AVL 平衡二叉树
AVL 树通过在插入过程中的旋转逻辑,使得树的自身高度差严格控制在 1 之内,从而解决了退化成 list 的问题。但是,频繁的旋转增加了树构建的成本<br>
BRT (red black tree) 红黑树
为了降低树构建时的成本,红黑树诞生了。红黑树通过将节点设定成 Red or Black,和同一条边中 Black 节点的数量相同等约束条件,在保证了树基本平衡的情况下,优化了自旋转流程
二叉树
是N(N>=0)个结点的有限集合,该集合或为空集(空二叉树),<br>或者由一个根结点和两颗互不相交的、分别称为根结点的左子树<br>和右子树的二叉树组成。
满二叉树
所有分支结点都存在左子树和右子树,并且所有非叶子节点都在同一层上
完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号i(1<= i <= n)的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同,则这棵二叉树称为完全二叉树
huffman tree 哈夫曼树<br>
哈夫曼树,又被称为最优二叉树,属于带权值二叉树的一种。它的真实节点全部分布在叶子节点中,是各种可能的组合中 WPL 值最小的形式。组合形式可能不唯一,但 WPL 值一定为最小。WPL(Weighted Path Length),也就是 带权路径长度,说简单一些就是【节点到根节点的路径长度 * 该节点的权值】。说白了就是权值越大的节点,离根节点越近就对了<br>
散列表查找
二分查找
插值查找
斐波那契查找
哈希查找
字符串匹配
朴素
KMP
Robin-Karp
Boyer-Moore
AC自动机
trie(前缀树和压缩前缀树)
后缀树
评论
0 条评论
下一页