1. 内存的工作原理

计算机内存的工作原理，就像是很多抽屉的集合体，每个抽屉都有地址

需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址

需要存储多次数据时，有两种基本方式——数组和链表

2. 数组和链表

使用数组意味着所有待办事项在内存中都是相连的

①链表

链表中的元素可存储在内存的任何地方

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。只要有足够的内存空间，就能为链表分配内存

链表的优势在插入元素方面

② 数组

* 排行榜网站使用卑鄙的手段增加页面浏览量。他们不在一个页面中显示整个排行榜，而将排行榜的每项内容都放在一个页面中，并让你单击Next来查看下一项

链表存在类似的问题。在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2获取元素#3的地址，以此类推，直到访问最后一个元素。

需要读取所有元素时，链表的效率很高，但如果你需要跳跃，链表的效率真的很低

数组与此不同：你知道每个元素的地址

随机的读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问到第五个元素。

③术语

数组的元素带编号，编号从0而不是从1开始

元素的位置称为索引

④在中间插入

要让待办事项按日期排序，现在要根据新增的待办事项的日期将其插入到正确的位置

1> 使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址

2> 使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素时，链表是更好的选择

⑤ 删除

删除元素时，链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而数组删除元素后，后面的元素都会向前移

如果内存中没有足够的空间，插入操作可能失败，但在任何情况下都能够将元素删除

常见数组和链表操作的运行时间

仅当能够立即访问要删除的元素时，删除操作的运行时间才为O（1），链表中我们都记录了第一个元素和最后一个元素，删除这些元素时运行时间也为O(1)

数组：支持随机访问（用的很多）

链表：只能顺序访问（第一个元素开始逐个的读取元素）

扩展：链表数组

这个数组包含26个元素，每个元素都指向一个链表

3. 选择排序

假如你的计算机存储了许多乐曲，记录了每个乐队的作品被播放的次数，要将列表按播放次数从多到少的顺序排序，该如何做？

一种方法便是:遍历这个列表，找出播放次数最多的乐队，并将该乐队添加到一个新列表中，再次这样做，找出第二多的乐队，继续这样做，将得到一个有序列表，则需要的总时间为O（n*n），即O（n^2）

需要检查的元素越来越少

随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一个。既然如此，运行时间为什么还是O（n^2）？

第一次需要检查n个元素，但随后检查的元素数依次为 n-1，n-2，……，2,1.平均每次检查的元素数为（1/2）*n，则运行时间为O（n*(1/2)*n）,但大O表示法省略诸如（1/2）这样的常数，因为写为O（n*n或O（n^2）

* 排序算法是一种灵巧的算法，但其速度不是很快，快速排序是一种更快的排序算法，其运行时间为O（nlogn）

4. 代码示例

def findSmallest(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 = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

测试：

print(selectionSort([5, 3, 6, 2, 10]))

运行结果

[2, 3, 5, 6, 10]

5. 小结

①计算机内存犹如一大堆抽屉

②需要存储多个元素时，可使用数组和链表

③数组的元素都在一起

④数组的读取速度很快

⑤链表的元素是分开的，其中每个元素都存储下一个元素的地址

⑥链表的插入和删除速度很快

⑦在同一个数组中，所有元素的类型都必须相同（都为int、double）