算法与数据结构-数组

(文章目录)

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

  这个定义中有几个关键词。如果你理解了这些关键词，我想你可以完全掌握数组的概念。

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

  与之相反的概念是非线性表，如二叉树、堆叠、图纸等。之所以被称为非线性表，是因为数据之间的前后关系在非线性表中并不简单。

  我们拿一个长度 10 的 int 类型的数组 int[] a = new int以[10]为例。在我画的这张照片中，计算机给了数组 a[10]连续内存空间分配 1000～其中，内存块的第一个地址是1039 base_address = 1000。  我们知道，计算机将为每个内存单元分配一个地址，计算机通过地址访问内存中的数据。当计算机需要随机访问数组中的一个元素时，它首先通过以下搜索公式计算元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

  其中 data_type_size 表示数组中每个元素的大小。在我们举的例子中，数组中存储的是 int 所以类型数据 data_type_size 就为 4 字节。这个公式很简单，我就不多解释了。

  假设数组的长度为 n，现在，如果我们需要在数组中插入一个数据 k 位置。为了把第一个 k 腾出一个位置，给出新的数据，我们需要把它放在第一位 k～n 这部分元素顺序向后移动。插入操作的时间复杂度是多少？你可以先试着自己分析一下。

  若将元素插入数组的末尾，则无需移动数据，此时时间复杂度为 O(1)。但是如果元素插入到数组的开头，所有的数据都需要依次向后移动，所以最坏的时间复杂性是 O(n)。 因为我们在每个位置插入元素的概率是一样的，所以平均时间复杂度是 (1+2+...n)/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 这些数据将被移动三次，我们可以首先记录已删除的数据。每个删除操作并不是真正移动数据，而是记录数据已被删除。当数组没有更多的空间存储数据时，我们触发了一个真正的删除操作，这大大减少了由删除操作引起的数据移动。

  对于数组类型，许多语言提供容器类型，如 Java 中的 ArrayList、C++ STL 中的 vector。在项目开发中，什么时候适合数组，什么时候适合容器？

  这里我拿 Java 以语言为例。如果你是的话。 Java 工程师几乎每天都在用 ArrayList，应该很熟悉。与数组相比，它有什么优势？

  我个人认为，ArrayList 最大的优点是可以包装许多数组操作的细节。例如，上述数组在插入和删除数据时需要移动其他数据。此外，它还具有支持动态扩展的优势。

  由于需要分配连续的内存空间，数组本身在定义时需要提前指定大小。如果我们申请大小为 10 数组，当第 11 当一个数据需要存储在数组中时，我们需要重新分配一个更大的空间，复制原始数据，然后插入新数据。

  如果使用 ArrayList，我们根本不需要关心底层的扩容逻辑，ArrayList 它已经帮助我们实现了。每次存储空间不够时，它都会自动将空间扩展到 1.5 倍大小。

  然而，这里需要注意的是，扩展操作涉及内存应用程序和数据移动，这是相对耗时的。因此，如果需要提前确定数据的大小，最好创建它 ArrayList 提前指定数据大小。

  作为一名高级语言编程师，数组无用吗？当然不是。有时候，使用数组更合适。我总结了一些我自己的经验。

• Java ArrayList 基本类型不能存储，例如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 有一定的性能消耗，所以如果你特别关注性能，或者想使用基本类型，你可以选择数组。
• 若数据大小事先已知，且数据操作非常简单，则无法使用 ArrayList 提供的大多数方法也可以直接使用数组。
• 另一个是我个人的喜好。当我想表达多维数组时，使用数组往往更直观。例如 Object[][] array；如果使用容器，则需要这样定义：ArrayList > array。

  对于业务开发，直接使用容器就足够了，节省时间和精力。毕竟，性能损失不会影响系统的整体性能。但如果你做了一些非常底层的开发，比如开发网络框架，性能优化需要做到极端，数组将优于容器，成为首选。