数组和链表
当需要将数据存储到内存的时候，我们请求计算机提供存储空间，计算机给我们一个存储地址。需要存储多项数据的时候，有两种基本方式——数组和链表。
数组
想象画面
java 中一开始要确定数组的大小，不是没有道理的…
- 两个人去电影院看电影，找到地方就座后，又来了一个朋友，但是你们下一个位置是别人占用了，你们三个是好朋友，没理由分开，只得挪去其他有三个位置的地方。
- 所以来了新朋友是很麻烦的，但是有一种解决办法就是预先买了 10 个座位的，但是这样会浪费资源，要是超过 10 个还是转移（数组插入很麻烦）
- 但是我想知道另外一个朋友坐哪里，这是很简单的，挨在一起（数组查找快）
- 另一个朋友要走的话也很麻烦，因为剩下的朋友要往前来挨在一起坐，反正不管怎样大家是个整体，坐在一起就对了（数组删除很麻烦）
链表
链表和数组不一样，一定要顺序排着队这样。链表的元素可以存储在内存中的任何地方，当前元素存储存储着下一个元素的地址，从而使得一系列随机的内存地址串在了一起
想象画面
- 寻宝游戏：前往第一个地址，那有宝箱，打开后是下一个宝箱的地址。
- 但是我直接想要最后一个宝箱，是无法做到的，是要一个个查找直到倒数第二个才得到最后一个宝箱的位置（链表查找效率很低）
- 移走一个宝箱很容易，直接把上一个宝箱的地址指向下一个的地址就可以了（链表删除很快）
- 如果是五个人去看一部很火的电影，但是根本就无法坐一起，但是换做链表，就可以分开来做，所以这个来了新朋友一点也不麻烦（链表的优势就是插入）
运行时
这里是最差的情况，比如数组插入一个刚好就要移走（因为原来已经满了）
| 数组 | 链表 | |
|---|---|---|
| 插入 | O(n) | O(1) |
| 读取 | O(1) | O(n) |
| 删除 | O(n) | O(1) |
- O（n）是线性时间，O（1）是常量时间
选择排序
场景
- qq 音乐列表里面记录了每个音乐的播放次数，你要对它进行排序，从多到少
- 一种办法是遍历这个列表，然后找到播放次数最多的，然后添加到一个新列表
- 然后删除刚刚那个次数最多的，再继续这样找到第二多的
- 需要检查的就越来越少
算法复杂度（运行时）
- 第一次每个元素都查看一次，那就是执行 n 次
- 第二次执行 n-1 次
- 依次查看最后得出，要执行 n（n-1）（n-2）..2*1=n*1/2*n
- 但是大 O 表示法省略常数，所以最后是 O(n^2)