数组

  上一篇讲解了复杂度分析，在进入具体的算法训练之前，先来看一下我们最常用的一种数据结构，数组。

一、内存模型

  数组是一种线性数据结构，它会在内存中申请一段连续的空间，并在其中存入相同类型的数据。
（图片来自https://www.cnblogs.com/xiaoyouPrince/p/8043798.html，我懒得画了😂，意思明白就好。）

image.png

二、 复杂度分析

  刚学完复杂度分析，怎么能不对数组来搞一波呢。我们从对数组的增、删、改、查来看。

1. 增

  为了保证数据在内存上的连续性，如果要在数组中的某个位置上插入一个新的数据，就要将这个位置后面所有的数据向后移动一位，然后再添加这个新的数据。那这个操作的时间复杂度是多少呢？
  分两种情况，如果插入的数据在数组的最后一位，那不用移动任何的数据，直接插入就可以了，时间复杂度O(1)。如果是数组的中间位置或数组第一位，那就需要将后面所有的数据移动，时间复杂度O(n)。
  这里涉及到最优时间复杂度和最差时间复杂度的概念，很简单，最后一位插入就是最优时间复杂度O(1)，第一位插入就是最差时间复杂度O(n)。

2. 删

  删除操作的时间复杂度与增加是一样的，最优时间复杂度O(1)，最差时间复杂度O(n)。那为什么这里要把删除操作单独拿出来说呢。
  在进行数组删除操作的时候，如果我们对数组中数据的连续性要求不高，那就可以先把要删除的数据标记，当数组存满了之后，再一次性的删除所有需要删除的数据。

image.png

  如上图所示，如果要清除前两位数据，为了避免将3，4，5，6这几位数字搬移两次，我们可以现将这两位标记，等数据存满了之后，再将这两位一起删除，剩下的数据只需要搬移一次即可。这其实也是JVM标记清除垃圾回收算法的核心思想。

3. 改

  数组是一种线性表，内存连续且存储同一类型的数据，因此数组拥有一个杀手级特性，就是数组元素可随机访问。
  什么意思呢，就是说你可以随意的访问数组，就像：

int[] a = new int[]{1, 2, 3};
for (int i = 0; i < a.length; i++) {
    System.out.println(a[i]);
}

  利用数组下标，我们想访问哪个元素就访问哪个，时间复杂度O(1)。用数学公式表达的话就是：a[i]_address = base_address + i * data_type_size。

  那这里抛出一个问题，为什么数组的下标是从0开始的呢？

  数组下标的本质是偏移量，如果数组下标从1开始，那上述的那个公式就变成了a[i]_address = base_address + (i - 1) * data_type_size，可以看到，这里我们增加了一次减法操作，对于数组这种非常基础的数据结构，应该想尽办法减少运算复杂度，所以数组的下标就从0开始啦。

4. 查

  查找数组元素的时间复杂度与具体的算法有关。顺序遍历的时间复杂度为O(1)，二分查找的时间复杂度O(logn)等。

三、包装类

  很多编程语言都为数组提供了包装类，里面封装了很多常用的方法，例如java中使用频率非常高的ArrayList。那使用ArrayList有什么问题呢？
  ArrayList仅支持Integer等包装类，在对数组进行操作的时候就会涉及到拆包，装包等等一系列操作。当然如果对系统运行时间要求并不是那么严的话ArrayList是非常方便的。另外再提一句，ArrayList支持动态扩容，当数组容量不够用时，会申请原内存1.5倍大小的新空间，并将原数组中所有的数据复制过去。