文章参考:https://zhuanlan.zhihu.com/p/78094287
数组是一个有限的、类型相同的数据的集合，在内存中是一段连续的内存区域。
如下图:
数组的下标是从0开始的，上图数组中有6个元素，对应着下标依次是0、1、2、3、4、5，同时，数组里面存的数据的类型必须是一致的，比如上图中存的都是数字类型。
数组中的全部元素是“连续”的存储在一块内存空间中的，如上图右边部分，元素与元素之间是不会有别的存储隔离的。
另外，也是因为数组需要连续的内存空间，所以数组在定义的时候就需要提前指定固定大小，不能改变。
（在高级编程语言中，往往都使用动态数组来解决这个问题，所谓动态数组就是自动会进行数组扩容，当数组容量达到某个临界点的时候，动态数组会开辟一个更大的数组，然后将原来的元素复制过去。eg:OC 的 可变数组）
数组的访问:
数组在访问操作方面有着独特的性能优势，因为数组是支持随机访问的，也就是说我们可以通过下标随机访问数组中任何一个元素，其原理是因为数组元素的存储是连续的，所以我们可以通过数组内存空间的首地址加上元素的偏移量计算出某一个元素的内存地址，如下：
array[n]的地址 = array数组内存空间的首地址 + 每个元素大小*n
通过上述公式可知：数组中通过下标去访问数据时并不需要遍历整个数组，因此数组的访问时间复杂度是 O(1)，当然这里需要注意，如果不是通过下标去访问，而是通过内容去查找数组中的元素，则时间复杂度不是O(1)，极端的情况下需要遍历整个数组的元素，时间复杂度可能是O(n)，当然通过不同的查找算法所需的时间复杂度是不一样的。
数组的插入与删除:
因为数组元素的连续性要求，所以导致数组在插入和删除元素的时候效率比较低。
如果要在数组中间插入一个新元素，就必须要将要相邻的后面的元素全部往后移动一个位置，留出空位给这个新元素。还是拿上面那图举例，如果需要在下标为2的地方插入一个新元素11，那就需要将原有的2、3、4、5几个下标的元素依次往后移动一位，新元素再插入下标为2的位置，最后形成新的数组是：
23、4、11、6、15、5、7
如果新元素是插入在数组的最开头位置，那整个原始数组都需要向后移动一位，此时的时间复杂度为最坏情况即O(n)，如果新元素要插入的位置是最末尾，则无需其它元素移动，则此时时间复杂度为最好情况即O(1)，所以平均而言数组插入的时间复杂度是O(n)
数组的删除与数组的插入是类似的。
总结:
数组的访问效率高，插入与删除效率低。想改善数组的插入与删除效率可「 链表 」来实现。
若有收获，就点个赞吧
0 人点赞
