数组（Array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。
1.常用操作
1-1.初始化
js
/* 初始化数组 */
const arr = new Array(5).fill(0) // [0, 0, 0, 0, 0]
const nums = [1, 3, 2, 5, 4]1-2.插入
js
/* 在数组的索引 index 处插入元素 item */
function insert(arr, item, index) {
// 把索引 index 以及之后的所有元素向后移动一位
for (let i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1]
}
// 将 item 赋给 index 处的元素
arr[index] = item
}1-3.删除
js
/* 删除索引 index 处的元素 */
function remove(arr, index) {
// 把索引 index 之后的所有元素向前移动一位
for (let i = index; i < arr.length - 1; i++) {
arr[i] = arr[i + 1]
}
}1-4.访问
js
/* 随机访问元素 */
function randomAccess(arr) {
// 在区间 [0, arr.length) 中随机抽取一个数字
const random_index = Math.floor(Math.random() * arr.length)
// 获取并返回随机元素
const random_num = arr[random_index]
return random_num
}1-5.查找
js
/* 在数组中查找指定元素 */
function find(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i
}
return -1
}1-6.扩容
在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。
因此在大多数编程语言中，数组的长度是不可变的。
js
/* 扩展数组长度 */
// 请注意，JavaScript 的 Array 是动态数组，可以直接扩展
// 为了方便学习，本函数将 Array 看作长度不可变的数组
function extend(nums, enlarge) {
// 初始化一个扩展长度后的数组
const res = new Array(nums.length + enlarge).fill(0)
// 将原数组中的所有元素复制到新数组
for (let i = 0; i < nums.length; i++) {
res[i] = nums[i]
}
// 返回扩展后的新数组
return res
}2.优缺点
2-1.优点
- 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
- 支持随机访问：数组允许在
O(1)时间内访问任何元素。 - 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
2-2.缺点
- 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
- 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
- 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。
3.应用
- 随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
- 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
- 查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到
ASCII码的映射，则可以将字符的ASCII码值作为索引，对应的元素存放在数组中的对应位置。 - 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
- 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。