算法图解（2）

数组，向量，链表

每个内存对应地址，对象根据数据类型分配内存，按照字节存储在内存中，指针对象存储对象对应的内存地址

1. 数组

数组是一种线性数据结构，由一组连续的内存位置组成，数组的每个元素可以通过索引（下标）来直接访问。

优点：快速随机访问：空间利用率高

缺点：插入和删除操作效率低，固定大小

适用场景

• 对插入、删除操作要求不高，数组是较好的选择。
• 如果数据量在初始化时已知且不会发生较大变化，数组能够提供高效的存储和访问。

2. 链表

链表是一种线性数据结构，由一组节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。根据链接的方式，链表分为单向链表、双向链表和循环链表。

优点:插入和删除操作效率高：动态调整大小：

缺点：随机访问效率低：额外的内存开销：每个节点除了存储数据，还需要存储指针，增加了额外的内存开销。

适用场景

• 如果需要频繁插入或删除元素，链表能够提供更高效的操作。

• 如果数据量不确定，链表能够更灵活地应对大小的变化，而不需要像数组一样重新分配内存。

2. 向量

std::vector 是 C++ 标准模板库（STL）中的一种动态数组，提供了数组的所有功能，并且支持动态扩展和自动管理内存。

优点:动态调整大小,自动内存管理,丰富的操作接口

缺点:额外的内存开销,性能开销

3. 数组与链表的对比

3. 数组与向量的对比

选择排序（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]);
        }
    }
}