数据结构与算法——数组

为什么数组要从0开始编号，而不是从1开始？

如何实现随机访问？

1.什么是数组

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

①线性表

顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。

相对立的非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

②连续的内存空闲和相同类型的数据

相同类型保证数组元素内存地址的计算公式可以成立，从而支持随机访问。
优点：正因为这两个限制，数组才有了一个特性：随机访问（并不是random的随机，可能理解为任意访问更清晰一点。）。
缺点：但是，要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

2.数组是如何实现根据下标随机访问数组元素的？

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size(元素类型长度)

注意：数组和链表的区别

“链表适合插入、删除，时间复杂度是O(1)；数组适合查找，查找时间复杂度是O(1)。”实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为O(1)，即便是排好序的数组，二分查找的时间复杂度最好也是O(logn)。正确的表述应该是，“数组支持随机访问，根据下标随机访问的时间复杂度是O(1)。”

3.低效的“插入”和“删除”

数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效，那，为什么会导致低效？改进方法？

插入操作

假设现在有一个数组，长度为n，现在我们需要把一个数组插入到数组中的第k个位置。为了把第k个位置腾出来给信赖的数据，需要将第k~n这部分元素都顺序地往后挪一位。这样的话，插入操作的时间复杂度是多少？
最好情况：如果在数组的末尾插入元素，就不需要移动数据，这时的时间复杂度是O(1)。
最坏情况：如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是O(n)。
平均情况时间复杂度为(1+2+……+n)/n=O(n)。

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须搬移k之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，要将某个数据插入到第k个位置，为了避免大规模的数据搬移，简单办法是：直接将第k为数据搬移到数组元素的最后，把新的元素直接放入第k个位置。

这样，在特定场景下，在第k个位置插入一个元素的时间复杂度就降为O(1)。这个处理思想在快排中会用到。

删除操作

跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然数组中间会出现空缺，内存就不连续了。
如果要删除数组末尾的数据，则最好情况时间复杂度为O(1)；删除数组开头的数据，最坏情况时间复杂度为O(n)；平均情况时间复杂度为O(n)。

在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率也许会提高很多。
假设数组a[10]中存储了8个元素：a,b,c,d,e,f,g,h。现在，我们要依次删除a,b,c三个元素。

为了避免d,e,f,g,h这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
而这，正是JVM垃圾回收之标记——清除算法的思想。
标记——清除算法：从堆栈和静态存储区出发，遍历所有的引用，进而找出所有存活的对象。每当它找到一个存活对象，就会给对象设一个标记，这个过程不会回收任何对象。只有全部标记工作完成的时候，清理动作才会开始。在清理过程中，没有标记的对象将被释放，不会发生任何复制动作。所以剩下的堆空间是不连续的。标记——清除算法只有在少量垃圾产生时会很高效。

4.警惕数组的访问越界问题

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;
}

这段C语言代码的运行结果并非是打印三行“hello world”，而是会无限打印“hello world”。
因为，数组的大小是3，a[0],a[1],a[2],而这段代码书写错误，导致for循环的结束条件错写为了i<=3而不是i<3，所以当i=3时，数组a[3]访问越界。
在C语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据前面提到的数组寻址公式，a[3]也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量i的内存地址，那么a[3]=0就相当于i=0，就导致代码无限循环。

为什么a[3]的内存地址正好是变量i的内存地址

函数体内的局部变量存在栈上，且是连续压栈。这段代码的变量压栈顺序是：i,arr[0],arr[1],arr[2]。变量i最先入栈，然后是数组元素，因为数组地址连续从小到大，实际栈中的变量顺序为：arr[0],arr[1],arr[2],i。这样arr[3]的地址刚好与i相同。
另外的解释是：与编译器的实现有关。linux的gcc有一个编译选项(-fno-stack-protector)用于关闭堆栈保护功能。默认情况下启动堆栈保护，不管i声明在前还是声明在后，i都会在数组之后压栈，只会循环4次；如果关闭了堆栈保护功能，则会出现死循环。

数组越界在C语言中是一种未决行为(没有定义的行为)，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质是访问一段连续内存，只要数组通过偏移计算得到的内存地址时可用的，那么程序就可能不会报任何错误。
Java本身就会做越界检查，数组越界会抛出java.lang.ArrayIndexOutOfBoundsException。

5.容器能否完全替代数组？

针对数组类型，java提供了ArrayList容器类，C++STL中的vector。
拿java的ArrayList举例。ArrayList最大的优势就是可以将很多数组操作的细节封装起来，比如对数组的插入、删除操作。
另外就是支持动态扩容。数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间，如果申请的大小不够，就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。如果使用ArrayList，就不需要关心底层的扩容逻辑，ArrayList每次存储空间不够的时候，就会将空间自动扩容为1.5倍。需要注意的是，因为扩容操作涉及内存申请和数据搬移，是比较耗时的，所以如果事先能确定需要存储的数据大小，最好在创建ArrayList时事先指定大小。
1.java的ArrayList无法存储基本类型，涉及到拆装箱，会有一定性能消耗，涉及到技能或需要使用基本数据类型，选用数组。
2.如果数据大小事先已知，且对数据的操作简单，可以用数据。
3.多维数组表示时，数组更直观。Object[][] array和容器ArrayList array。

6.为什么数组要从0开始编号，而不是从1开始？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移(offset)”。
如果用a来表示数组的首地址，a[0]就是偏移为0的地址，也就是首地址，a[k]表示偏移了k个type_size的位置，所以a[k]的内存地址计算只需要：

a[k]_address = base_address + k * type_size

如果，数组从1开始奇数，那计算a[k]的内存地址变为：

a[k]_address = base_address + (k-1)*type_size

对比两个公式，从1开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令。

7.二维数组元素的地址计算公式

//行优先
a[i][j] = a[0][0] + i * n * data_type_size + j * data_type_size