数组
数组是一种最基础的数据结构，本文整理自极客时间相关课程，主要目的是把一些给我印象深刻的点记录下来。
数组是什么
数组（Array）是一种线性表数据结构。它用一组连续的内存，来存储一组具有相同类型的数据。
- 线性表
- 连续内存空间
- 相同类型
线性表
形象地来看，线性表就是数据排成像一条线一样的结构，并且最多只有前和后两个方向。数组、链表队列、栈等都是线性表结构。
与其对立的概念是非线性表，如二叉树、堆、图等。在非线性表中，数据之间并不是简单的前后关系。
连续的内存空间和相同类型的数据
- 因为这两个限制，数组具有了 “随机访问” 特性。
- 在数组中删除、插入数据，需要做大量数据搬移工作。
如何根据下标随机访问数组元素？
一维数组：a[i] = base_address + i * data_type_size
其中data_type_size指数据中每个元素的大小。例如：
a[0] = base_address + 0 * data_type_size
a[1] = base_address + 1 * data_type_size
a[2] = base_address + 2 * data_type_size
a[n] = base_address + n * data_type_size
上面对应的计算方式是数组下标从0开始的情况。
在大多数编程语言中，数组都是从0开始编号的。设想一下如果数组下标是从1开始呢？
a[1] = base_address + （1-1） * data_type_size
a[2] = base_address + （2-1） * data_type_size
a[3] = base_address + （3-1） * data_type_size
a[n] = base_address + （n-1） * data_type_size
对比可以发现，如果数组从1开始编号：则每次随机访问元素都多了一次减法操作，表达式相比之下比较复杂。
通过下标访问数组是非常基础的操作，从效率优化的角度考虑，为了减少一次减法操作，数据选择了从0开始编号，而不是从1开始；从历史角度考虑，C设计者用0开始计数数组下标，其他语言就沿袭下来了这个设计。
数组中的操作
数组的查找时间复杂度
在和链表最对比时往往会说 “链表插入删除O(1)查找O(n)，数组插入删除O(n)查找O(1)”。
这种说法是有问题的，确切的说，数组是随机访问（即通过下标访问指定位置元素）的时间复杂度是O(1)，而在数组中查找指定元素（比如说找数组中2这个元素在哪里）的时间复杂度一般来说并不是O(1)。
- 对于排序好的数组来说，可以使用二分查找，其查找复杂度是 O(log n)
- 对于无序数组来说，还是得遍历数组，其查找复杂度是 O(n)
数组的插入操作
在数组中末尾插入元素，时间复杂度是O(n)。
在数组中指定位置插入元素，如果需要保持原数组元素的顺序，则时间复杂度是O(n)；如果不需要保持原数组元素的顺序，可以把该指定位置元素放到数组末尾，将待插入元素放进指定位置，这样时间复杂度是O(1)。（快排中有用到这个思想）
数组的删除操作
在数组的删除操作中，为了内存的连续性，需要做很多数据搬移工作。一般来说，删除数组末尾元素，最好时间复杂度O(1)；删除数组开头元素，最坏时间复杂度O(n)。
为了改善删除操作的效率，我们可以将多次删除操作集中在一起执行：
- 每次删除操作并不真正搬移数据，只记录数据已经被删除。
- 当数组中已经没有更多空间存储数据时，再触发一次真正的删除操作。
- 这样就大大减少了删除操作导致的数据搬移。
- JVM的垃圾回收算法中的标记-清除算法就是这么做的。
容器和数组
Java中我们惯用ArrayList，其底层是一个可以动态增长的数组。ArrayList和数组相比，优势在于：
- 将很多数组操作的细节封装起来
- 支持动态扩容
在使用数组时，我们必须预先指定数组大小。并且如果要加入的元素数量大于指定的数组大小，还要申请一个更大的空间，将原来的数据复制进去。而使用ArrayList则不用这样，因为其内部有自动扩容机制。
但是扩容操作涉及内存申请和数据搬移，其实是很耗时的。容器将这些操作包装起来，为程序员提供了一个简单的接口，虽然使得编程更加容易，但容易使人忽略其内部实现，而不同的使用方法会有不同的效率。所以在使用容器的时候，我们要稍微关注一下其内部实现，尤其关注一些比较耗时的操作。看看有没有比较好的使用方式，可以减少这些耗时操作。比如说在ArrayList中虽然不用指定大小，但预先知道需要向其中放大量数据时，建议在创建ArrayList时指定大小。这样可以减少扩容次数，而扩容是非常耗时的。
数组和容器相比，使用数组更适合的场景：
- ArrayList等容器类都是无法存储基本类型的，对于int、long等基本类型只能存储器对应包装类，而在自动装箱和自动拆箱中会带来性能消耗。所以在关注性能的场景下，需要存储基本类型时，使用数组。
- 如果数据大小事先知道，并且对数据操作简单，可以直接使用数组。
- 多维数组用数组表示更直观，用容器不够直观。
- 业务开发用容器，框架开发追求性能用数组。