一、数组和链表
1.数组：
- 一个数组中的所有元素在内存中必须是相连的
- 同一个数组中的所有元素类型必须相同（int、double等）
优点
需要随机读取元素时，效率很高
缺点
在数组中插入元素比较慢，需要把后面的元素都后移，如果空间不够，就必须转移到内存的其他地方。
2. 链表
- 链表中的元素可以放在内存的任意位置
- 链表中前一个元素存放着下一个元素的地址
优点
a. 快速插入元素，只需要改变前一个元素指向的地址
b. 删除元素只需要改变前一个元素指向的地址
缺点
当要读取链表的最后一个元素时，你必须从头开始读取。因为不知道最后一个元素的位置，所以必须先访问元素#1，从而获取第二个元素的地址，以此类推，最后找到最后一个元素的地址，所以读取速度很慢。
总结
链表在随机插入元素和删除元素的速度上要快于数组，但读取元素数组更快。
二、选择排序
选择排序就是遍历一个列表，找到其中最大或最小的一个元素添加到一个新的列表中，再遍历列表剩余元素，找到最小的元素添加到新列表，直到把所有元素都添加到新列表中。
def find_smallest(arry):
length = len(arry)
# 存储最小的值
smallest = arry[0]
# 存储最小元素的索引
smallest_index = 0
for i in range(1, length):
if smallest > arry[i]:
smallest = arry[i]
smallest_index = i
return smallest_index
def select_sort(arry):
new_list = []
for i in range(len(arry)):
print(len(arry), i)
# 找到最小的元素的索引
smallest_index = find_smallest(arry)
# 把这个最小元素添加到新列表中，并在原列表中删除
new_list.append(arry.pop(smallest_index))
return new_list
if __name__ == "__main__":
print(select_sort([4, 3, 2, 1]))
