数据结构与算法（04）（数组）数据结构与算法（04）：数组

前言
每一种编程语言中，几乎都有数组这种数据类型。不过它不仅仅是一种数据类型，同时还是一种基础的、很常见的数据结构。看着很简单，但是还是希望借助这次对数据结构与算法的系统学习，能够再学习一下数组相关的内容。对于数组的学习将从下面几个菜单对应的内容开始。
数组如何实现高效的随机访问
什么是数组？这个问题大家心里肯定都有答案。用专业的话来解释：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。这个定义里面有几个关键词，理解了这几个词，也就可以彻底掌握数组。
第一是线性表，顾名思义，线性表就是数据排列成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。

文章图片
image.png 而与他相对立的是非线性表，比如二叉树、图、堆等。之所以叫非线性表，是因为在非线性表中，数据之间并不是只有简单的前后关系。

文章图片
image.png 第二个关键词是连续的内存空间和相同类型的数据。正是因为有了这俩个限制，数组才有了一个非常强大的特性：支持“随机访问”。但有利也有弊，也正是因为这两个限制，使得数组的很多操作变得非常低效，比如要想在数组中插入或者删除一个元素，为了保证内存地址连续性，就必须要做大量的数据搬移工作。
说到数据的访问，那数组到底是如何根据数组下标访问对应位置的元素呢？
我们那一个长度为10的int型数组 int[] intArray = new int[10] 来举例，在下面这张图中假设计算机给数组intArray分配了一块连续的内存空间1000~1039，其中内存块的首地址为base_address=1000.

文章图片
image.png 我们知道，计算机会给每个内存单元分配一个地址，计算机通过这个分配的地址来访问对应位置的数据。当计算机需要随机访问指定位置的数据时，需要先通过下面的寻址公式，来计算出该数组下标对应元素在内存中的地址：

a[i]_address = base_address + i * data_type_size

其中data_type_size表示数组中元素类型对应的长度。我上面这个例子，计算机需要访问intArray[5]时，首先通过寻址公式计算出下标5对应内存中的地址为 intArray[5]_address = 1000 + 5*4 = 1020.即下标5对应的内存地址为 [1020 , 1020 + 4 - 1],即1020 ~ 1023.
对于查找操作，即使我们用最快的二分查找，时间复杂度也是O(log n)。但是数组支持随机寻址访问元素，所以根据下表随机访问的时间复杂度为 O(1).
低效的插入和删除
前面概念部分提到，数组为了保持内存数据的连续性，会导致插入和删除非常的低效。那么为什么会导致低效？对此又有哪些改善的办法？
我们先看插入操作
假设一个数组的长度为n，现在我们需要将一个元素插入到数组的第K个位置。为了把第K个位置的数组腾出来，我们需要将K~N的全部数据整体往后移一位。这样一来，插入的时间复杂度是多少呢？
假设我们是在末尾插入一个元素，那不需要移动任何原有的元素，这时的时间复杂度为O(1).但是如果是在数组的开头插入元素，这也是最坏的情况，时间复杂度为O(n)。因为我们在每个位置插入元素的概率是不一样的，所以插入操作的时间复杂度为（1+2+3+……+n）/n , 平均时间复杂度为 O（n）。
如果这个数组内的元素是有序的，那在第K个位置插入，我们就需要将位置K及K之后的所有元素向后移动一位。但是，如果数组中的数据没有任何规律，我们只是拿它当做一个存储数据的容器，那在这种情况下有一种优化的方式，我们可以直接将第K个位置的元素移动到数组的末尾，进而腾出第K个位置用于插入元素，这样可以避免大规模的数据搬移，这样一来可以将数组的插入时间复杂度降低到O(1)。
再来看看删除操作
有了对插入操作的理解，删除操作也就不难理解了。删除第K个位置的元素，需要将K后面的所有元素向前挪1位，如果删除末尾元素则时间复杂度为O（1），删除其他位置时间复杂度O(n), 平均时间复杂度还是O(n)。
看一个例子，假设我们要删除intArray的前四个元素：

文章图片
image.png 为了避免为了避免后面的4，5，6，7几个元素被搬移4次，我们可以先记录下已经删除的数据，即每次删除操作并不是正在的搬移数据，只是记录数据已经被删除。当数据没有更多空间存储数据时，我们在触发一次真正的删除操作，这样可以大大减少删除操作导致的数据搬移。
如果有了解过JVM的垃圾回收算法，应该能发现这不就是垃圾回收算法中的标记——清除算法思想吗。这样又一次证明了数据结构与算法的重要性，无处不在的。
容器能否完全代替数组
“容器能否完全代替数组？”这是一个很值得让我们思考的问题，比如Java中的ArrayList等，那么在项目开发中，什么时候用数组，什么时候用容器呢？
这里我拿 Java 语言来举例。作为一名Java工程师，我几乎每天都会用ArrayList，对它也非常熟悉，当然也知道ArrayList的底层或者说本质其实也还是个数组。那么它与数组相比，又有哪些优劣势呢？
个人觉得，ArrayList最大的优势就是：可以将很多数组操作的细节封装起来，用起来更方便了，比如前面提到的查询、插入、删除等。另外ArrayList的另一大优势便是：ArrayList支持数组的动态扩容，这将为我们省去很多处理数组越界的逻辑。
而数组的话，它本身在定义的时候需要指定大小，因为需要分配连续的内存空间，如果我们申请了一个大小为10的数组，那么需要插入第11个元素的时候，我们能做的只有重新申请一个更大的数组，然后把旧的10个数组在copy到新数组，最后在插入新元素。
如果使用ArrayList，我们完全不需要关心底层的数组扩容逻辑，ArrayList已经帮我们实现了。每次申请的空间不够的时候，它会自动扩容1.5倍。但是需要注意的是数组的扩容将设计的内存空间的申请及数据的搬移，这是一个非常耗时的操作，所以如果我们在使用容器的时候，如果能够确定大小，也尽量指定大小。
那么对于高级语言来说，数组是不是就没有用武之地了？当然不是，有些时候，用数组会更适合些，大概总结了几点：
1.Java ArrayList无法存储基本数据类型，如：int、long等，需要封装为Integer、Long等。而封箱/拆箱有一定的性能损耗，所以如果特别注重性能，希望使用基本类型时，可以选择数组。
2.如果数据量大小事先已知，并且操作比较简单，用不到复杂的操作，可以直接用数组。
3.当要表示多维数组时，用数组往往更为直观（这个就要看个人喜好了）。
总结一下，如果普通的业务开发那使用ArrayList没有任何问题，也不会影响到你整体的性能。但是如果是偏向底层的开发，比如网络框架等，性能的优化非常注重，这种建议使用数组。
为什么数组的下标是从0开始的呢？
从人类的思维角度，第一个位置应该是1，那为什么数组的下标是从0开始的呢？
（1）从数组的内存模型角度来看，下标的含义是位置偏移, 这样的话用a[0]表示第一个元素就很好理解了，因为第一个元素的位置偏移肯定是0.
（2）回想我们上面的寻址公式，如果从1开始的话，寻址公式就会变为：

a[i]_address = base_address + (i-1) * data_type_size

很显然这样会多增加一步减法运算，对CPU来说，是多了一步减法指令。
（3）应该是历史问题，从java的角度来看，java比c出现的晚，而历史的语言比如c语言中已经定义了0作为第一个元素的下标，在Java中也定义为0有助于C语言程序员学习Java（这都是猜测，如果这么说的话那数组在诞生的时候又为什么要定义为0呢，难道是第一个创造的人随意定义的吗？搞不懂了……）
【数据结构与算法（04）（数组）】个人网站：relaxheart网