数据结构与算法之美（三）：数组

数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。

一、 如何实现随机访问

1） 数组是一种线性数据结构，用连续的存储空间存储相同类型数据：
I） 线性表：数组、链表、队列、栈 ；非线性表：树、图
II） 连续的内存空间、相同的数据，所以数组可以随机访问，但对有序数组进行删除、插入，为了保持数组的有序性， 就要做大量的数据搬移工作。

a) 数组如何实现下标随机访问。

引入数组在内存中的分配图，得出寻址公式：a[i]_address = base_address + i * data_type_size

b) 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。
正确表述：数组支持随机访问，根据下标随机访问的时间复杂度为O（1）

二、低效的插入和删除

1） 有序插入：从最好O(1) 最坏O(n) 平均O(n)；
2） 无序插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)；
3） 有序删除：从最好O(1) 最坏O(n) 平均O(n)；
4） 多次删除集中在一起，提高删除效率：
记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

三、警惕数组的访问越界问题

用C语言循环越界访问的例子说明访问越界的bug：

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存，那么内存中的i将会被置为0，则为死循环永远出不去。

四、容器能否完全替代数组

针对数组类型，很多编程语言都提供了容器类，比如C++ STL 的vector，java 的ArrayList，容器最大的优势是将数组的操作封装起来了，比如数组的删除和插入操作，还有就是容器支持动态扩容。当然数组也有其适合使用的场景。
数组适合的场景：
1） Java ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别在乎性能，可以考虑数组；
2） 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组；
3） 表示多维数组时，数组往往更加直观；
4） 业务开发容器即可。底层开发，如网络框架，性能优化等，选择数组。

五、解答数组下标为什么从0开始

从0开始编号，数组元素的寻址公式是：
a[k]_address = base_address + k * type_size

从1开始编号，数组元素的寻址公式是：
a[k]_address = base_address + (k-1)* type_size

从寻址公式上来看，从一开始编号，每次寻址计算都增加了一个k-1的运算，对于CPU来说就是多了一次减法指令，数组作为基础的数据结构，效率肯定要做到极致，所以数组选择了从0开始编号。当然上面说的也不一定是压倒性证明，也可能有一定的历史原因。