1. 链表
- 链表中的元素可存储在内存的任何地方。而数组的元素都在一起
- 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一
起。
链表元素在内存中的存储.png
2. 链表和数组的区别
- 需要同时读取所有元素时，链表的效率很高
- 需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素
3. 下图是常见数组和链表操作的运行时间
image.png
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
# 利用findSmallest函数实现选择排序算法
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]))
