数组

1.什么是数组?

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

2.数组的插入和删除

数组的插入最好时间复杂度为O(1),最坏的时间复杂度为O(n),平均时间复杂度为O(n).

数组插入的改善方法:当数组存储的无序数据时,可以将插入的值直接放入,把替换的值放入到数组的末尾.

数组的删除的最好时间复杂度为O(1),最坏的时间复杂度为O(n),平均时间复杂度为O(n).

数组插入的改善方法:当数组删除时,并不是真正的删除.只是标记为删除.只有当插入数据数组存储不下时开始真正的清除

数组中标记为删除的数据.多次删除集中在一起,提高效率.

3.数组为什么可以根据下标随机访问?

首先数组是一个连续的内存空间.然后可以根据  a[i]_address = base_address + + i * data_type_size.这个公式在知道了

下标的情况下取出存储的值.

多维数组的寻址公式: 若二维数组大小为m*n，那么寻址公式为a[i][j]_address = base_address + (i * n+j)*data_type_size

4. 容器能否完全替代数组?

相比于数字，java中的ArrayList封装了数组的很多操作，并支持动态扩容。一旦超过村塾容量，扩容时比较耗内存，

因为涉及到内存申请和数据搬移。

数组适合的场景：
1） Java ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别管柱性能，可以考虑数组
2） 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组
3） 表示多维数组时，数组往往更加直观。
4） 业务开发容器即可，底层开发，如网络框架，性能优化。选择数组。

5.数组的下标为什么要从0开始?

1.首先数组的寻址公式为a[k]_address = base_address + k * type_size.若下标从1开始则公式将变为

a[k]_address = base_address + (k-1)*type_size.每次随机访问数组元素都多了一次减法运算，对于 CPU 来说

就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非基础的编程操作，

效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始.

2.最主要的原因还是因为

C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，

为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。

本文是在学习王争老师的数据结构与算法之美的笔记.有些是王争老师或者评论的言语.在此附上原文链接

 https://time.geekbang.org/column/article/40961