数组
数组是程序设计中最基础的数据结构，它把相同类型的数据按连续的内存位置有序存放，通过下标就能快速访问对应元素，便于批量存储与处理一组数据，但数组长度大多固定，插入删除操作效率相对较低。
数据结构1分钟阅读
数组（Array） 是计算机科学中最基础、最核心的线性数据结构（Linear Data Structure）。它用一块连续的内存空间，来存储一组具有相同类型的数据。
数组最核心的两大特点：内存连续分配、存储元素类型完全相同。
以 C++ 的int数组为例，int类型每个元素占用 4 字节。当定义整型数组时，全部元素会在内存里紧密相邻、依次排布。
示例：int arr[] = {11, 9, 17, 89, 1, 90, 19, 5, 3, 23, 43, 99}，它在内存中的排布如下：
因为数组在内存中是连续存放的，计算某个元素的物理内存地址非常高效：
- ：数组起始内存地址（即下标为
0的地址）。 - ：单个元素占用的内存字节数（如
int占用 4 字节）。 - 下标 的本质：表示该元素相对于首地址的偏移量（Offset）。如果从
0开始，寻址公式只需一次乘法和一次加法。
| 操作 | 时间复杂度 | 机制与原因 |
|---|---|---|
| 随机访问 (Access) | 通过寻址公式直接计算物理内存地址，一步到位 | |
| 按值查找 (Search) | 无序数组需要逐个遍历；若已排序，二分查找可优化至 | |
| 末尾插入 / 删除 | 直接在末尾操作，不需要移动其他元素 | |
| 中间插入 / 删除 | 为保持连续性，插入时需将后续元素向后平移；删除时需向前平移 |
- 超高读取效率：支持根据下标 随机访问。
- CPU 缓存友好（Cache Locality）：因为数据连续存放，CPU 预取机制会将其批量加载到 Cache，大幅提升访问性能。
- 空间利用率高：不需要像链表那样额外存储指向下一个元素的指针。
- 插入/删除成本高：平均需要平移一半的元素（）。
- 空间连续性要求高：如果内存碎片严重，即使剩余总内存足够，也可能因为找不到足够大的连续内存而分配失败。
- 频繁查询，极少增删：如存储一周 7 天的名称、常量对照表、查找表。
- 多维数据建模：如矩阵运算、图像像素数据（二维数组/RGB 三维数组）。
- 作为其他数据结构的底层实现：栈（Stack）、队列（Queue）、哈希表（Hash Table）、堆（Heap）等很多复杂数据结构都是基于数组构建的。