选择排序：
具体思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
def Is_Sort(arr): #判断是否排好序
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
return False
return True
def Select_Sort(arr):
for i in range(len(arr)):
smallest_index = i
for j in range(i+1, len(arr)):
if arr[j] < arr[smallest_index]:
smallest_index = j #找到右侧最小值得索引
arr[smallest_index], arr[i] = arr[i], arr[smallest_index]
return arr
nums = [randint(1,100) for i in range(1000)] #随机生成100个[1-100]的数
start = time.time()
sort_num = Select_Sort(nums)
print(sort_num)
end = time.time() - start #测试排序所需时间
print(end)
print(Is_Sort(sort_num))
数组和链表:
1数组是通过元素的位置进行读取的，所以在读取方面效率高。
在插入和删除元素时，由于需要移动元素后面的位置，效率没有链表高
2链表中的每个元素都存储了下一个元素的地址，使一系列随机的内存地址都串在一起，这就导致了读取时效率低，其优势在于插入和删除两方面。
常见数组和链表操作的运行时间
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
小结:
数组都是在一起的
链表都是分开的，其中每个元素都存储了下一个元素的地址
数组读取速度很快
链表在插入和删除速度很快
