企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文是 AlgoNote「算法通关手册」中 数组基础 的深度解读。文章以数组的定义与内存模型为起点，系统讲解随机访问的寻址原理、多维数组的组织方式、不同编程语言中的实现差异，并结合仓库源码与配套题解，带读者完整掌握数组「增、删、改、查」四类基本操作及其时间复杂度，为后续学习排序、二分查找、双指针、滑动窗口等数组进阶算法打下坚实基础。

1. 数组是什么：线性表与连续内存空间的结合

1.1 数组定义

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

简而言之，数组是「线性表顺序存储结构」的典型代表。以整数数组为例，假设数组包含 $n$ 个元素，每个元素都有唯一的下标索引，范围从 $0$ 到 $n - 1$，每个下标对应一个数据元素。

数组在计算机中本质上是一段连续的内存区域：每个元素占用相同大小的存储单元，这些单元都有自己的内存地址，并且在物理内存中依次排列。正因为「连续」与「同构」这两个特性，数组才能通过简单的地址计算实现高效的随机访问。

1.2 从「线性表」视角理解数组

线性表是一种数据元素顺序排列、类型相同的数据结构，每个元素最多只有前驱和后继两个相邻元素。数组正是线性表的一种典型实现。除了数组之外，栈、队列、链表等也属于线性表结构，它们在逻辑上都呈现"一维有序"的特征，区别主要在于物理存储方式与操作限制。

1.3 从「存储结构」视角理解数组

线性表有「顺序存储」和「链式存储」两种方式：

• 顺序存储：要求内存空间连续，相邻元素在物理内存中紧挨着。数组采用的就是这种方式，且所有元素类型一致，因此每个元素占用的存储单元大小相同，可以直接用「首地址 + 偏移量」定位。
• 链式存储：不要求物理连续，通过指针或引用把逻辑相邻的元素串联起来（如链表），代价是额外的指针开销与更慢的随机访问。

综合两个角度：数组 = 采用顺序存储结构实现的线性表。这也是它在"随机访问"上优于链表、在"插入删除"上劣于链表的内在原因。

2. 随机访问的原理：寻址公式

数组最显著的特点是支持随机访问：可以通过下标直接定位并访问任意一个元素，而无需从头遍历。那么计算机是如何做到这一点的？

1. 数组在内存中被分配为一段连续空间，第一个元素的地址称为首地址（记为base）。
2. 每个元素类型一致、占用字节数相同（记为size）。
3. 访问下标为 $i$ 的元素时，通过寻址公式直接计算其内存地址：

下标 $i$ 的元素地址 = 首地址 + $i$ × 单个元素占用的字节数

即addr(nums[i]) = base + i * size

由于地址计算只涉及一次乘法与一次加法，与数组长度 $n$ 无关，因此随机访问的时间复杂度恒为 $O(1)$。这也是数组在需要频繁按下标取值的场景（如排序中的比较、二分查找中的取中值）中被广泛使用的原因。

需要强调的是，这里的 $O(1)$ 针对的是按下标访问；如果要求"查找某个值为 $val$ 的元素"，由于不确定目标位置，仍需线性遍历，复杂度为 $O(n)$（详见下文 5.2 节）。

3. 多维数组：数组的数组

前面介绍的是只有一个维度的数组，称为一维数组，每个数据元素通过单一下标访问。但在实际应用中，许多数据具有二维或多维结构（如图像像素、矩阵、表格），一维数组无法满足需求，因此引入了多维数组。

以二维数组为例：它由 $m$ 行 $n$ 列的数据元素组成，本质上可以理解为「数组的数组」——第一维表示行，第二维表示列，每个元素本身也是一个数组（一维数组）。

在内存中，二维数组通常采用两种方式排布：

• 行优先（Row-major）：先存完第一行，再存第二行……C / C++、Python（嵌套 list）等多数语言默认行优先。行优先下，元素matrix[i][j]的地址 = 首地址 +(i * n + j) * size。
• 列优先（Column-major）：先存完第一列，再存第二列……Fortran 等语言采用列优先。

二维数组常被视为矩阵，用于处理矩阵转置、矩阵加法、矩阵乘法等问题。仓库配套题解中的 0048. 旋转图像、0054. 螺旋矩阵、0498. 对角线遍历 正是以二维数组/矩阵为载体考察下标映射规律的经典题目。

4. 不同编程语言中数组的实现差异

数组的"连续存储、同类型"定义在不同语言中落地程度不同。理解差异有助于避免跨语言移植时的认知错位。

4.1 C / C++：最贴合定义的数组

C / C++ 语言中的数组实现最贴合数据结构教材中对数组的定义：使用一块连续的内存空间存储相同类型的数据元素，无论是基本数据类型还是结构体、对象，都按连续方式排列。多维数组采用行优先连续排布，例如：

int arr[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};

由于 C/C++ 数组退化为指向首元素的指针，且不自动记录长度，下标越界属于未定义行为，需要程序员自行保证0 <= i < n。

4.2 Java：连续存储但支持不规则数组

Java 的数组同样存储相同类型数据，底层连续存储，并自带长度属性length，下标越界会抛出ArrayIndexOutOfBoundsException。与 C/C++ 不同的是，Java 的多维数组本质是「数组的数组」，允许创建不规则数组（jagged array），即每个嵌套数组的长度可以不同：

int[][] arr = new int[3][]; arr[0] = new int[]{1, 2, 3}; arr[1] = new int[]{4, 5}; arr[2] = new int[]{6, 7, 8, 9};

4.3 Python：用 list 充当数组

原生 Python 中并不存在严格意义上的「数组」数据结构，最常用的是列表（list），功能类似于 Java 的ArrayList。与经典数组相比，Python list 有以下特点：

• 可以存储不同类型的数据元素；
• 长度可以动态变化（本质是动态数组，尾部追加均摊 $O(1)$，扩容时整体搬移）；
• 支持丰富的内置方法（append、pop、insert、index等）。

例如：

arr = ['python', 'java', ['asp', 'php'], 'c']

说明：若确需"同类型 + 紧凑内存"的数值数组，Python 标准库还提供了array模块与numpy.ndarray，但本手册及配套算法代码均以 list 作为数组的通用载体。

4.4 三种实现对比

5. 数组的基本操作：增、删、改、查

数组的基本操作主要包括四类：查（访问 / 查找）、改（改变）、增（插入）、删（删除）。以下代码均使用 Python list 模拟数组，完整可运行。

5.1 访问元素（$O(1)$）

访问数组中第 $index$ 个元素：先检查下标是否在合法范围 $0 \le index \le len(nums) - 1$ 内；合法则直接按下标取值，非法则抛出异常或返回特殊值。

def get_element(nums: list[int], index: int): """获取数组中指定下标的元素值""" if 0 <= index < len(nums): return nums[index] else: raise IndexError(f"数组下标 {index} 超出范围 [0, {len(nums)-1}]") arr = [0, 5, 2, 3, 7, 1, 6] print(get_element(arr, 3)) # 输出: 3

访问操作不依赖数组中元素个数，因此时间复杂度为$O(1)$。

5.2 查找元素（$O(n)$）

查找数组中元素值为 $val$ 的位置：遍历数组，将 $val$ 与每个元素依次比较；找到返回下标，遍历完未找到返回特殊值（如 $-1$）。

def find_element(nums: list[int], val: int): """查找数组中元素值为 val 的位置""" for i in range(len(nums)): if nums[i] == val: return i return -1 arr = [0, 5, 2, 3, 7, 1, 6] print(find_element(arr, 5)) # 输出: 1 print(find_element(arr, 9)) # 输出: -1 (未找到)

当数组无序时，只能采用线性查找，需要遍历整个数组，时间复杂度为$O(n)$。若数组有序，则可改用二分查找将复杂度降到 $O(\log n)$，详见仓库章节 数组二分查找（一）。

5.3 插入元素（$O(n)$）

在数组第 $index$ 个位置插入值 $val$：先检查 $index$ 是否在 $0 \le index \le len(nums)$ 范围内；扩展数组长度腾出空间；将 $index$ 及其后的元素整体向后移动一位；最后在 $index$ 位置写入 $val$。

def insert_element(nums: list[int], index: int, val: int): """在指定位置插入元素""" if 0 <= index <= len(nums): # 扩展数组长度，在末尾添加一个占位元素 nums.append(0) # 将 index 及其后的元素整体向后移动一位 for i in range(len(nums) - 1, index, -1): nums[i] = nums[i - 1] # 在 index 位置插入 val nums[index] = val return True else: return False arr = [0, 5, 2, 3, 7, 1, 6] result = insert_element(arr, 2, 4) print(f"插入结果: {result}") # 输出: 插入结果: True print(f"插入后数组: {arr}") # 输出: [0, 5, 4, 2, 3, 7, 1, 6]

注意：这里用 Python 的append先扩展长度，再用循环完成从后往前的元素搬移。在数组中间位置插入时，移动元素次数与元素个数成正比，最坏和平均时间复杂度均为$O(n)$；只有在末尾追加（append）时才达到均摊 $O(1)$。

5.4 改变元素（$O(1)$）

将数组中第 $index$ 个元素值改为 $val$：检查下标合法性后直接赋值。

def change_element(nums: list[int], index: int, val: int): """修改数组中指定位置的元素值""" if 0 <= index < len(nums): nums[index] = val return True else: return False arr = [0, 5, 2, 3, 7, 1, 6] result = change_element(arr, 2, 4) print(f"修改结果: {result}") # 输出: 修改结果: True print(f"修改后数组: {arr}") # 输出: [0, 5, 4, 3, 7, 1, 6]

改变元素与访问元素一样通过下标直接定位，无需遍历，时间复杂度为$O(1)$。

5.5 删除元素（$O(n)$）

删除数组中第 $index$ 个位置的元素：检查下标 $0 \le index < len(nums)$ 是否合法；将 $index + 1$ 位置及其后的元素整体向前移动一位；删除最后一个元素（或更新数组长度）。

def delete_element(nums: list[int], index: int): """删除数组中指定位置的元素""" if 0 <= index < len(nums): # 将 index 后的元素整体向前移动一位 for i in range(index, len(nums) - 1): nums[i] = nums[i + 1] # 删除最后一个元素（或更新数组长度） nums.pop() return True else: return False arr = [0, 5, 2, 3, 7, 1, 6] result = delete_element(arr, 2) print(f"删除结果: {result}") # 输出: 删除结果: True print(f"删除后数组: {arr}") # 输出: [0, 5, 3, 7, 1, 6]

删除需要移动后续元素，移动次数与数组长度相关，时间复杂度为$O(n)$。

5.6 操作复杂度汇总

这一"读改写快、插入删除慢"的特性决定了数组的使用策略：以随机访问为主、增删尽量发生在尾部的场景适合数组；频繁在中间插入删除的场景则应考虑链表（见仓库章节 链表基础）。

6. 仓库源码印证：数组是算法实现的载体

在本仓库中，数组不仅是数据结构章节的主题，更是大量算法的直接载体。从源码结构看，codes/python/01_array/ 目录集中存放了基于数组的各类经典算法实现，可以作为理解数组操作与复杂度分析的活教材。

6.1 基于数组的排序算法

数组的随机访问能力使其成为排序算法最自然的宿主。仓库在 数组排序 章节及其后续各节中逐类展开，源码实现包括：

• 冒泡排序（array_sort_bubble_sort.py）：对数组未排序区间[0, n - i - 1]的元素做相邻比较与交换，并设置flag标志位，若某趟未发生任何交换则提前终止——体现了"就地修改数组元素"（改变操作 $O(1)$）的组合使用。
• 快速排序（array_sort_quick_sort.py）：以partition哨兵划分为核心，通过nums[i], nums[j] = nums[j], nums[i]这类下标交换在数组上完成元素重排，再递归处理左右子区间，深刻依赖数组按下标随机访问的能力。
• 此外还有选择、插入、希尔、归并、堆、计数、桶、基数排序等完整实现，全部以list为数组载体，见 codes/python/01_array/。

6.2 数组上的查找与区间算法

在掌握基本操作之后，数组相关的进阶算法也全部围绕"下标 + 区间"展开：

• 二分查找：利用随机访问 $O(1)$ 在有序数组上以 $O(\log n)$ 完成查找，见 数组二分查找（一）；
• 双指针：利用两个下标在数组上完成首尾相向或快慢同步遍历，见 数组双指针；
• 滑动窗口：本质是用两个指针维护连续子区间，将嵌套循环优化为单循环，见 数组滑动窗口。

7. 练习题目与进阶路径

7.1 配套练习题

数组基础部分的配套练习覆盖"基本操作、二维数组下标规律、区间处理"三个方向，仓库均提供完整题解，建议按顺序刷完：

• 0066. 加一：用数组模拟整数加一与进位，本质是"改变 + 边界进位"的综合练习（简单）；
• 0724. 寻找数组的中心下标：前缀和思想的入门题，两次遍历求左右侧和（简单）；
• 0189. 轮转数组：三次数组翻转完成原地轮转，空间复杂度 $O(1)$（中等）；
• 0048. 旋转图像：二维数组下标映射规律，原地旋转 90°（中等）；
• 0054. 螺旋矩阵：按顺时针边界模拟遍历二维矩阵（中等）；
• 0498. 对角线遍历：按"行号 + 列号"奇偶性找规律并处理边界（中等）。

更完整的数组分类题目清单（含数组操作、前缀和、双指针、滑动窗口、二分查找等子类）见 数组基础题目列表。

7.2 本章延伸章节

数组基础是 数组章节 的起点，后续按学习路径依次展开：

1. 数组排序 及其后的冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数排序各章；
2. 数组二分查找（一） 与 数组二分查找（二）；
3. 数组双指针 与 数组滑动窗口。

总结

数组是一种基础且重要的数据结构，采用连续内存存储同类型数据，最大优势在于支持随机访问：通过寻址公式「首地址 + 下标 × 元素字节数」即可在 $O(1)$ 时间内定位任意元素。数组的访问与修改操作时间复杂度为 $O(1)$，插入与删除因需要移动元素而为 $O(n)$。掌握这一"读快写慢"的特性，是理解排序、二分查找、双指针、滑动窗口等一切数组算法的基础，也是后续学习链表、栈、队列等线性结构时进行横向对比的锚点。

• 教程
• 文档
• 知识库