算法图解（2）
数组，向量，链表
每个内存对应地址，对象根据数据类型分配内存，按照字节存储在内存中，指针对象存储对象对应的内存地址
1. 数组
数组是一种线性数据结构，由一组连续的内存位置组成，数组的每个元素可以通过索引（下标）来直接访问。
优点：快速随机访问：空间利用率高
缺点：插入和删除操作效率低，固定大小
适用场景
- 对插入、删除操作要求不高，数组是较好的选择。
- 如果数据量在初始化时已知且不会发生较大变化，数组能够提供高效的存储和访问。
2. 链表
链表是一种线性数据结构，由一组节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。根据链接的方式，链表分为单向链表、双向链表和循环链表。
优点:插入和删除操作效率高：动态调整大小：
缺点：随机访问效率低：额外的内存开销：每个节点除了存储数据，还需要存储指针，增加了额外的内存开销。
适用场景
-
如果需要频繁插入或删除元素，链表能够提供更高效的操作。
- 如果数据量不确定，链表能够更灵活地应对大小的变化，而不需要像数组一样重新分配内存。
2. 向量
std::vector 是 C++ 标准模板库（STL）中的一种动态数组，提供了数组的所有功能，并且支持动态扩展和自动管理内存。
优点:动态调整大小,自动内存管理,丰富的操作接口
缺点:额外的内存开销,性能开销
3. 数组与链表的对比
| 特性 | 数组（Array） | 链表（Linked List） |
|---|---|---|
| 内存分配 | 连续分配 | 非连续分配 |
| 大小 | 固定 | 动态可变 |
| 访问时间复杂度 | O(1)（随机访问） | O(n)（必须遍历） |
| 插入/删除时间复杂度 | O(n)（最坏情况下） | O(1)（在给定节点处） |
| 内存利用率 | 高（没有额外指针开销） | 低（需要额外指针存储） |
| 适用场景 | 随机访问多，数据量固定 | 插入/删除多，数据量动态变化 |
3. 数组与向量的对比
| 特性 | 数组（Array） | 向量（std::vector） |
|---|---|---|
| 大小 | 固定大小 | 动态调整大小 |
| 内存分配 | 静态或动态，固定连续 | 动态，连续分配，但可能有额外空间 |
| 访问时间复杂度 | O(1) | O(1) |
| 插入/删除时间复杂度 | O(n) | O(1) 或 O(n)（视位置而定） |
| 内存开销 | 低 | 较高（为了支持动态调整） |
| 自动内存管理 | 不支持 | 支持 |
| 功能 | 基本功能 | 丰富的操作接口 |
| 适用场景 | 数据量固定，性能要求高 | 数据量不确定，灵活性要求高 |
选择排序（Selection Sort）（排序算法）
原理：每次从待排序的序列中选出最小（或最大）的元素，放到已排序序列的末尾，直到所有元素排序完毕。
优点：简单，节省空间
缺点：时间复杂度高，不稳定（打乱顺序）
时间：O(n²)
空间：O(1)
实例：给定向量，每次寻找n-i个元素中的最小值，并和i元素交换
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}