数组

计算机内存

计算机内存可以想象成一堆盒子，每个盒子上有连续的编号（内存地址）

连续编号的盒子

一维数组

数组存储一组类型相同的值

一个数组中的元素在内存中是连续存放的，使用数组时必须先分配内存空间

数组arr在内存中存储

如果初始化了一个长度是5的数组，需要存放6个元素时，那么就必须重新分配内存，如果下一个地址被占用，数组中的所有元素必须移动到能存下6个元素的连续地址内存中去

就好比5个人去电影院看电影，必须要坐在一起，这时如果来了第6个人，就必须再买一张票，旁边的坐位别人坐了，所有人都得挪到能坐下连续6个人的位置上去，或者不连着坐（链表）

增加数组元素，重新分配内存空间

如果这个数组只存放了4个元素，那么该数组依然占用5个内存空间

如果只去了4个人，那么第5个位置虽然是空的，但是别人不能再买第五个位置的票了（申请内存）

数组占用空间，但未使用

某些语言在底层处理内存分配，或者采用其他数据结构实现数组，所以在编写代码时，不用分配内存，没有长度限制，可随意添加元素，并且可存储不同类型的值

时间复杂度

数组连续存储的结构，使得数组的读取速度很快，读取数组中的任一元素的时间复杂度是O(1)

有数组 arr = [4, 5, 6]，4,5,6分别是数组的第1,2,3个元素，读取数组的第一个元素4用arr[0]，中括号中的0被称为数组索引，索引从0开始，访问第1,2,3个数组元素分别是arr[0],arr[1],arr[2]，访问arr[3]一般会出现数组越界的错误

定义好数组arr = [4, 5, 6]后，arr存储了数组开头，也就是数组第一个元素的内存地址，arr[0]其实是指arr + 0，所以arr[0]访问的是地址为arr的内存存放的东西，就是数组的第一个元素，以此类推arr[1]，就是arr + 1，访问数组中第2个元素

所以访问数组中任一元素，只用在首地址上加上一个数，如第100个元素就是arr + 99，所以读取数组任一元素的时间复杂度是O(1)

读取数组

查找和这里的访问元素不一样，查找是指已知某个元素的值，去查数组中有没有相同的值，乱序数组中[3, 1, 2]查找元素的时间复杂度是O(n)，在排好序的数组中[1, 2, 3]，使用二分查找的时间复杂度是O(logn)

插入和删除数组中的元素的时间复杂是O(n)，因为如果在数组第一个元素插入或删除元素，需要将数组中所有元素前移或后移一个位置，最好的情况是插入在数组最后面或者删除数组最后一个元素，所以插入或删除元素平均时间复杂度大概是O(n/2)，时间复杂度表示中，常量一般不计，故时间复杂度为O(n)

数组中插入元素

多维数组

二维数组可以考虑成有行和列的数组，也可以考虑成元素是数组的数组，二维数组用两个索引访问，如有二维数组 arr = [[4, 5], [6, 7]] 第一层数组是竖着堆放的盒子，第二层是横着排列的盒子，访问arr[0][0] == 4，arr[0][1] == 5，arr[1][0] == 6等，第一个索引0代表第一行，第二个索引1代表第2列

arr[i][j] 访问地址的方法是 arr + (length * i + j)，length是内存数组的长度或者二维数组的列数

多维数组以此类推

二维数组

总结

• 数组在内存中连续存放
• 数组每个元素类型相同
• 数组变量存储了数组第一个元素的地址
• 数组读取，插入，删除的时间复杂度分别是O(1)，O(n)，O(n)

参考

[1]. 算法图解 - 巴尔加瓦