1.1 基础数据结构：数组
数组是计算机科学中最基本的数据结构之一。如果你用过数组，那么应该知道它就是一个含有数据的列表。它有多种用途，适用于各种场景，下面就举个简单的例子。
一个允许用户创建和使用购物清单的食杂店应用软件，其源代码可能会包含以下的片段。
array=["apples", "bananas", "cucumbers", "dates", "elderberries"]
这就是一个数组，它刚好包含5个字符串，每个代表我会从超市买的食物。
此外，我们会用一些名为索引的数字来标识每项数据在数组中的位置。
在大多数的编程语言中，索引是从0算起的，因此在这个例子中，"apples"的索引为0,"elderberries"的索引为4，如下所示。
若想了解某个数据结构（例如数组）的性能，得分析程序怎样操作这一数据结构。
一般数据结构都有以下4种操作（或者说用法）。
❏ 读取：查看数据结构中某一位置上的数据。对于数组来说，这意味着查看某个索引所指的数据值。例如，查看索引2上有什么食品，就是一种读取。
❏ 查找：从数据结构中找出某个数据值的所在。对于数组来说，这意味着检查其是否包含某个值，如果包含，那么还得给出其索引。例如，检查"dates"是否存在于食品清单之中，给出其对应的索引，就是一种查找。
❏ 插入：给数据结构增加一个数据值。对于数组来说，这意味着多加一个格子并填入一个值。例如，往购物清单中多加一项"figs"，就是一种插入。
❏ 删除：从数据结构中移走一个数据值。对于数组来说，这意味着把数组中的某个数据项移走。例如，把购物清单中的"bananas"移走，就是一种删除。
本章我们将会研究这些操作在数组上的运行速度。
同时，我们也将学到本书的第一个重要理论：操作的速度，并不按时间计算，而是按步数计算。
为什么呢？
因为，你不可能很绝对地说，某项操作要花5秒。它在某台机器上要跑5秒，但换到一台旧一点的机器，可能就要多于5秒，而换到一台未来的超级计算机，运行时间又将显著缩短。所以，受硬件影响的计时方法，非常不可靠。
然而，若按步数来算，则确切得多。如果A操作要5步，B操作要500步，那么我们可以很肯定地说，无论是在什么样的硬件上对比，A都快过B。因此，衡量步数是分析速度的关键。
此外，操作的速度，也常被称为时间复杂度。在本书中，我们会提到速度、时间复杂度、效率、性能，但它们其实指的都是步数。
事不宜迟，我们现在就来探索上述4种操作方式在数组上要花多少步。
1.1.1 读取
首先看看读取，即查看数组中某个索引所指的数据值。
这只要一步就够了，因为计算机本身就有跳到任一索引位置的能力。在["apples","bananas", "cucumbers", "dates", "elderberries"]的例子中，如果要查看索引2的值，那么计算机就会直接跳到索引2，并告诉你那里有"cucumbers"。
计算机为什么能一步到位呢？原因如下。
计算机的内存可以被看成一堆格子。下图是一片网格，其中有些格子有数据，有些则是空白。
当程序声明一个数组时，它会先划分出一些连续的空格子以备使用。换句话说，如果你想创建一个包含5个元素的数组，计算机就会找出5个排成一行的空格子，将其当成数组。
内存中的每个格子都有各自的地址，就像街道地址，例如大街123号。不过内存地址就只用一个普通的数字来表示。而且，每个格子的内存地址都比前一个大1，如下图所示。
购物清单数组的索引和内存地址，如下图所示。
计算机之所以在读取数组中某个索引所指的值时，能直接跳到那个位置上，是因为它具备以下条件。
(1) 计算机可以一步就跳到任意一个内存地址上。（就好比，要是你知道大街123号在哪儿，那么就可以直奔过去。）
(2) 数组本身会记有第一个格子的内存地址，因此，计算机知道这个数组的开头在哪里。
(3) 数组的索引从0算起。
回到刚才的例子，当我们叫计算机读取索引3的值时，它会做以下演算。
(1) 该数组的索引从0算起，其开头的内存地址为1010。
(2) 索引3在索引0后的第3个格子上。
(3) 于是索引3的内存地址为1013，因为1010 + 3=1013。
当计算机一步跳到1013时，我们就能获取到"dates"这个值了。
所以，数组的读取是一种非常高效的操作，因为它只要一步就好。一步自然也是最快的速度。这种一步读取任意索引的能力，也是数组好用的原因之一。
如果我们问的不是“索引3有什么值”，而是“"dates"在不在数组里”，那么这就需要进行查找操作了。下面我们就来看看。
1.1.2 查找
如前所述，对于数组来说，查找就是检查它是否包含某个值，如果包含，还得给出其索引。那么，我们就试试在数组中查找"dates"要用多少步。
对于我们人来说，可以一眼就看到这个购物清单上的"dates"，并数出它的索引为3。但是，计算机并没有眼睛，它只能一步一步地检查整个数组。
想要查找数组中是否存在某个值，计算机会先从索引0开始，检查其值，如果不匹配，则继续下一个索引，以此类推，直至找到为止。
我们用以下图来演示计算机如何从购物清单中查找"dates"。
首先，计算机检查索引0。
因为索引0的值是"apples"，并非我们所要的"dates"，所以计算机跳到下一个索引上。
索引1也不是"dates"，于是计算机再跳到索引2。
但索引2的值仍不匹配，计算机只好再跳到下一格。
啊，真是千辛万苦，我们找到"dates"了，它就在索引3那里。自此，计算机不用再往后跳了，因为结果已经得到。
在这个例子中，因为我们检查了4个格子才找到想要的值，所以这次操作总计是4步。
这种逐个格子去检查的做法，就是最基本的查找方法——线性查找。第2章我们还会学习另一种查找方法。
但在那之前，我们再思考一下，在数组上进行线性查找最多要多少步呢？
如果我们要找的值刚好在数组的最后一个格子里（如本例的elderberries），那么计算机从头到尾检查每个格子，会在最后才找到。同样，如果我们要找的值并不存在于数组中，那么计算机也还是得查遍每个格子，才能确定这个值不在数组中。
于是，一个5格的数组，其线性查找的步数最大值是5，而对于一个500格的数组，则是500。
以此类推，一个N格的数组，其线性查找的最多步数是N（N可以是任何自然数）。
可见，无论是多长的数组，查找都比读取要慢，因为读取永远都只需要一步，而查找却可能需要多步。
接下来，我们再研究一下插入，准确地说，是插入一个新值到数组之中。
1.1.3 插入
往数组里插入一个新元素的速度，取决于你想把它插入到哪个位置上。
假设我们想要在购物清单的末尾插入"figs"。那么只需一步。因为之前说过了，计算机知道数组开头的内存地址，也知道数组包含多少个元素，所以可以算出要插入的内存地址，然后一步跳到那里插入就行了。图示如下。
但在数组开头或中间插入，就另当别论了。这种情况下，我们需要移动其他元素以腾出空间，于是得花费额外的步数。
例如往索引2处插入"figs"，如下所示。
为了达到目的，我们必须先把"cucumbers"、"dates"和"elderberries"往右移，以便空出索引2。而这也不是一步就能移好，因为我们首先要将"elderberries"右移一格，以空出位置给"dates"，然后再将"dates"右移，以空出位置给"cucumbers"，下面来演示这个过程。
第1步："elderberries"右移。
第2步："date"右移。
第3步："cucembers"右移。
第4步：至此，可以在索引2处插入"figs"了。
如上所示，整个过程有4步，开始3步都是在移动数据，剩下1步才是真正的插入数据。
最低效（花费最多步数）的插入是插入在数组开头。因为这时候需要把数组所有的元素都往右移。
于是，一个含有N个元素的数组，其插入数据的最坏情况会花费N + 1步。即插入在数组开头，导致N次移动，加上一次插入。
最后要说的“删除”，则相当于插入的反向操作。
1.1.4 删除
数组的删除就是消掉其某个索引上的数据。
我们找回最开始的那个数组，删除索引2上的值，即"cucumbers"。
第1步：删除"cucumbers"。
虽然删除"cucumbers"好像一步就搞定了，但这带来了新的问题：数组中间空出了一个格子。因为数组中间是不应该有空格的，所以，我们得把"dates"和"elderberries"往左移。
第2步：将"dates"左移。
第3步：将"elderberries"左移。
结果，整个删除操作花了3步。其中第1步是真正的删除，剩下的2步是移数据去填空格。
所以，删除本身只需要1步，但接下来需要额外的步骤将数据左移以填补删除所带来的空隙。
跟插入一样，删除的最坏情况就是删掉数组的第一个元素。因为数组不允许空元素，当索引0空出，那么剩下的所有元素都要往左移去填空。
对于含有5个元素的数组，删除第一个元素需要1步，左移剩余的元素需要4步。而对于500个元素的数组，删除第一个元素需要1步，左移剩余的元素需要499步。可以推出，对于含有N个元素的数组，删除操作最多需要N步。
既然学会了如何分析数据结构的时间复杂度，那就可以开始探索各种数据结构的性能差异了。了解这些非常重要，因为数据结构的性能差异会直接造成程序的性能差异。
下一个要介绍的数据结构是集合，它跟数组似乎很像，甚至让人以为就是同一种东西。然而，我们将会看到它跟数组在性能上是有区别的。