数组

在内存中开辟空间需要连接一起的空间

当加入新的数据时，内存空间不够需要重新分批一开可以连接一起的空间

知道一个元素位置可以知道所有元素位置

链表

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

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

要获取最后一个元素位置需要知道前面所有元素位置

选择排序

有一组歌单，按照歌曲播放次数，进行排序 选择排序：找出播放次数最多的歌曲，添加到一个新的列表中，依次找出播放次数第二的乐队 第一次需要检查 n 个元素，但随后检查的元素数依次为 n  1, n – 2, …, 2 和 1。平均每次检查的元素数为 1/2 × n，因此运行时间为 O(n × 1/2 × n)。但大 O 表示法省略诸如 1/2 这样的常数 ，为 O(n2)