- 定义
所谓数组，是有序的元素序列。 若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。
用于区分数组的各个元素的数字编号称为下标。 这些有序排列的同类数据元素的集合称为数组。
Type[] arrName = new Type[len]；
Type: 数组类型
arrName： 数组名，可以通过该变量访问数组的元素，记录的是该对象对应内存的起始位置。
index：下标，可以通过arrName[index]访问数组对应位置的元素（从0开始）。
len：定义数组的长度。
总的来说数组就是一块连续的内存空间用来存储相同类型的对象，此外数组的初始化一旦完成，数组所占的空间就完成固定下来了，因此数组的长度是不可变的。
- 基本使用
（1）数组的定义
数组的定义的语法格式包括以下两种，但是更加推荐使用第一种方式。
Type[] arrName；
Type arrName[];
（2）数组的初始化
Java中必须先初始化数组，然后才可以使用，所谓初始化，就是为数组的元素分配内存空间，并且为每个数组元素赋初始值。
数组的初始化方式包括两种，静态初始化和动态初始化。
a. 静态初始化：由程序员指定每个数组元素的初始值，有系统决定数组长度。
Type[] arrName = new Type[]{e1, e2, e3}; //注意：[]符号内部不能指定数组长度的值
Type[] arrName = {e1, e2, e3};
动态初始化：初始化时由程序员指定数组长度，由系统为数组元素分配初始化值。
Type[] arrName = new Type[10];
在执行动态初始化之后，程序员只需要指定数组的长度，系统将会为这些数组元素分配初始化值，默认规则如下:
基本类型对应的整数类型 ---- 0
基本类型对应的小数类型 ---- 0.0
基本类型对应的字符类型 ---- '\u0000'
基本类型对应的布尔类型 ---- false
复杂类型 ---- null
（3）使用数组
如果想要访问数组中对应下标位置的元素，只需要提供对应的索引即可，注意索引是从0开始的。
arrName[2]; //访问数组中索引为 2 位置对应的元素
arrName[2] = e; //将 e 放到数组中 下标为 2 对应的位置
数组其实就是一个对象，在创建一个数组时，其对象头除了保存锁标志、哈希码、所属类型之外，还会保存该数组的长度，所以数组的长度是不可变的。数组名实际上指向的是该对象所在的内存空间的起始位置的地址，所以取下标为 index 对应的下标位置的元素，则会使用startAddress + index * elementSize获取对应位置的地址，所以只需要 O(1)的复杂度就可以获取到。
- 扩展
在之前的定义中提到过，数组的长度是不可变的，所以我们可以提供自定义的数组类，使其可以根据数据的大小自动调整数组的长度。
public class Array <T> {
private T[] data;
private int size;
public Array(int capacity){
this.data = (T[])new Object[capacity];
}
public Array(){
this(5);
}
//数组扩容 | 缩容，新容量为 capacity
private void resize(int capacity){
data = Arrays.copyOf(data, capacity);
}
//移除指定索引的元素
public T remove(int index){
if(index < 0 || index >= size) throw new IllegalArgumentException("无效的 index");
T ret = data[index];
size --;
for (int i = index; i < size ; i++) {
data[i] = data[i+1];
}
return ret;
}
//向指定索引添加元素
public void add(int index, T t){
if(index < 0 || index > size) throw new IllegalArgumentException("无效的 index");
if(size == data.length) resize(data.length * 2);
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = t;
size ++;
}
......
}
添加元素时最好的情况下时间复杂度为 O(1)，最坏情况下时间复杂度为 O(n)因为涉及到数组的扩容，平均复杂度为 O(1)，因为每 n 次才会出现一次扩容，所以平均复杂度为 O(2)也就是 O(1)。
但是可能会出现如下这种情况，导致添加和移除元素的复杂度都变为了 O(n)。
出现以上情况的原因是缩容的太过着急，我们应该采用延迟策略，也就是当数组的元素变为容量的 1/2 时，我们不进行缩容操作，而是等到数组的元素变为容量的 1/4 时，才将数组的容量变为原来的 1/2,。
