1. 内存的工作原理
计算机内存的工作原理，就像是很多抽屉的集合体，每个抽屉都有地址
需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址
需要存储多次数据时，有两种基本方式——数组和链表
2. 数组和链表
使用数组意味着所有待办事项在内存中都是相连的
①链表
链表中的元素可存储在内存的任何地方
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。只要有足够的内存空间，就能为链表分配内存
链表的优势在插入元素方面
② 数组
* 排行榜网站使用卑鄙的手段增加页面浏览量。他们不在一个页面中显示整个排行榜，而将排行榜的每项内容都放在一个页面中，并让你单击Next来查看下一项
链表存在类似的问题。在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2获取元素#3的地址，以此类推，直到访问最后一个元素。
需要读取所有元素时，链表的效率很高，但如果你需要跳跃，链表的效率真的很低
数组与此不同：你知道每个元素的地址
随机的读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问到第五个元素。
③术语
数组的元素带编号，编号从0而不是从1开始
元素的位置称为索引
④在中间插入
要让待办事项按日期排序，现在要根据新增的待办事项的日期将其插入到正确的位置
1> 使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址
2> 使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素时，链表是更好的选择
⑤ 删除
删除元素时，链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而数组删除元素后，后面的元素都会向前移
如果内存中没有足够的空间，插入操作可能失败，但在任何情况下都能够将元素删除
常见数组和链表操作的运行时间
| 数组 | 链表 | |
读取 |
O（1） | O（n） |
| 插入 | O（n） | O（1） |
| 删除 | O（n） | O（1） |
仅当能够立即访问要删除的元素时，删除操作的运行时间才为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）
