一、数组和链表

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]))