数据结构——数组

数组

数组是最基本的数据结构，数组是存储在连续内存空间上的相同类型数据的集合。在数组中，可以方便地通过下标索引的方式去获取对应的数据。举一个字符数组的例子，如下图所示：

需要注意的是：

正因为数组在内存空间的地址是连续的，所以删除或者增添元素时难免要移动其他元素的地址，

所以数组中的元素不能删除，只能覆盖。

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

数组的删除和插入操作都比较低效。

先看看插入操作。

比如需要将一个数据插入到数组中的第k个位置，假设数组长度为n，为了把第k个位置腾出来给新来的数据，我们需要将第k - n 这部分的元素都顺序地往后挪一位，时间复杂度可就不简单了。

如果是在数组末尾插入元素，那就不需要移动数据，时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为(1+2+…)/n = O(n)。

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。

在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。

为了更好地理解，我们举一个例子。假设数组 a[10]中存储了如下 5 个元素：a，b，c，d，e。

我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5]，将 a[2]赋值为 x 即可。最后，数组中的元素如下： a，b，x，d，e，c。

利用这种处理技巧，在特定场景下，在第 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标记清除垃圾回收算法

数组是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的在特点是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是如果是特别底层的开发，直接使用数组可能会更合适。

在数组中，可以用到的算法技巧就有很多了，比如双指针、双指针的变种快慢指针、滑动窗口、二分查找等，还有很多排序算法也是根据数组来进行排序的。