程序员时时刻刻需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存 储多项数据时，有两种基本方式——数组和链表。但它们并非都适用于所有的情形，因此知道它 们的差别很重要。接下来介绍数组和链表以及它们的优缺点。
（2.1） 数组和链表
有时候，需要在内存中存储一系列元素。假设你要编写一个管理待办事
项的应用程序，为此需要将这些待办事项存储在内存中。
应使用数组还是链表呢?鉴于数组更容易掌握，我们先将待办事项存 储在数组中。使用数组意味着所有待办事项在内存中都是相连的(紧靠在 一起的)。
数组.png
现在假设你要添加第四个待办事项，但后面的那个抽屉放着别人的东西!
添加.png
这就像你与朋友去看电影，找到地方就坐后又来了一位朋友，但原来坐的地方没有空位置， 只得再找一个可坐下所有人的地方。在这种情况下，你需要请求计算机重新分配一块可容纳4个 待办事项的内存，再将所有待办事项都移到那里。
如果又来了一位朋友，而当前坐的地方也没有空位，你们就得再次转移!真是太麻烦了。同 样，在数组中添加新元素也可能很麻烦。如果没有了空间，就得移到内存的其他地方，因此添加 新元素的速度会很慢。一种解决之道是“预留座位”:即便当前只有3个待办事项，也请计算机提 供10个位置，以防需要添加待办事项。这样，只要待办事项不超过10个，就无需转移。这是一个 不错的权变措施，但你应该明白，它存在如下两个缺点。
- 你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不了。
- 待办事项超过10个后，你还得转移。
因此，这种权宜措施虽然不错，但绝非完美的解决方案。对于这种问题，可使用链表来解决
（2.2）链表
链表中的元素可存储在内存的任何地方。
链表.png
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
串在一起的内存地址.png
这犹如寻宝游戏。你前往第一个地址，那里有一张纸条写着“下一个元素的地址为123”。因 此，你前往地址123，那里又有一张纸条，写着“下一个元素的地址为847”，以此类推。在链表 中添加元素很容易:只需将其放入内存，并将其地址存储到前一个元素中。
使用链表时，根本就不需要移动元素。这还可避免另一个问题。假设你与五位朋友去看一部 很火的电影。你们六人想坐在一起，但看电影的人较多，没有六个在一起的座位。使用数组时有 时就会遇到这样的情况。假设你要为数组分配10 000个位置，内存中有10 000个位置，但不都靠 在一起。在这种情况下，你将无法为该数组分配内存!链表相当于说“我们分开来坐”，因此， 只要有足够的内存空间，就能为链表分配内存。
链表的优势在插入元素方面，那数组的优势又是什么呢?
（2.3）数组
排行榜网站使用卑鄙的手段来增加页面浏览量。它们不在一个页面中 显示整个排行榜，而将排行榜的每项内容都放在一个页面中，并让你单击 Next来查看下一项内容。例如，显示十大电视反派时，不在一个页面中显 示整个排行榜，而是先显示第十大反派(Newman)。你必须在每个页面中 单击Next，才能看到第一大反派(Gustavo Fring)。这让网站能够在10个页 面中显示广告，但用户需要单击Next 九次才能看到第一个，真的是很烦。 如果整个排行榜都显示在一个页面中，将方便得多。这样，用户可单击排行榜中的人名来获得更 详细的信息。
链表存在类似的问题。在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道 它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3 的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高:你读 取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率 真的很低。
数组与此不同:你知道其中每个元素的地址。
需要随机地读取元素时，数组的效率很高，因为可迅 速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。
（2.4）数组、链表运行时间
下面列出了常见的数组和链表操作的运行时间。
运行时间.png
问题:在数组中插入元素时，为何运行时间为O(n)呢?假设要在数组开头插入一个元素，该怎么做呢？？？很显然，当在第一个元素之前插入元素的时候，后面的所有元素都要往后移动一位。。
（2.4.1）在中间插入
需要在中间插入元素时，数组和链表哪个更好呢?使用链表时，插入元素很简单，只需修改 它前面的那个元素指向的地址。
而使用数组时，则必须将后面的元素都向后移。
如果没有足够的空间，可能还得将整个数组复制到其他地方!因此，当需要在中间插入元素 时，链表是更好的选择。
（2.4.2）删除
如果你要删除元素呢?链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。
不同于插入，删除元素总能成功。如果内存中没有足够的空间，插入操作可能失败，但在任 何情况下都能够将元素删除。
我们来看一下数组和链表的操作运行时间：
运行时间.png
需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。通常我 们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1)。
数组和链表哪个用得更多呢?显然要看情况。但数组用得很多，因为它支持随机访问。有两 种访问方式:随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只 能顺序访问:要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机 10 访问意味着可直接跳到第十个元素。
（2.5）选择排序
假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作
品被播放的次数。
[图片上传中...(WechatIMG2.jpeg-338e39-1548642302636-0)]
你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢?
一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中
WechatIMG2.jpeg
需要的总时间为 O(n × n)，即O(n2)。
按照这种逻辑，需要检查的元素数越来越少，每次都少检查一个元素，最后一次需要检查的元素都只有一 个。运行时间怎么还是O(n2)？
并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素 数依次为n , n-1, n – 2, ..., 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。 但大O表示法省略诸如1/2这样的常数,因此简单地写 作O(n × n)或O(n2)。
选择排序是一种灵巧的算法，但其速度不是很快
示例代码
# 前面没有列出对乐队进行排序的代码，但下述代码提供了类似的功能:将数组元素按从小到 大的顺序排列。先编写一个用于找出数组中最小元素的函数。
def findSmalest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
# 现在可以使用这个函数来编写选择排序算法了。
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmalest(arr)
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 2, 44, 33]))
结果如下：
/usr/local/bin/python3.6 /Users/tsoumac2016/Desktop/算法Python/findSmallest.py
[2, 3, 5, 33, 44]
Process finished with exit code 0
小结：
- 计算机内存犹如一大堆抽屉。
- 需要存储多个元素时，可使用数组或链表。
- 数组的元素都在一起。
- 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快。
- 链表的插入和删除速度很快。
- 在同一个数组中，所有元素的类型都必须相同(都为int、double等)。
网友评论