这是《算法图解》的第二篇读书笔记，内容主要涉及数组、链表及选择排序。
1.数组
1.1定义
作为一种基础的数据结构，数组指的是n个元素按照索引号依次存放在一个内存区域的数据结构。其中，索引号相邻的元素在内存的位置也是相邻的。
1.2优缺点
1.2.1优点
支持随机访问。即可根据索引号访问与之对应的元素，从而实现快速访问数组中的元素。
1.2.2缺点
(1)删除、插入元素慢。若要删除或插入元素，则需移动制定元素后面的所有元素。
(2)有溢出的可能。数组的内存不足后，需要将整个数组迁移至容量更大的内存中。
1.3适用范围
需要快速访问元素、但对插入、删除元素的速度要求不高的场景。
2.链表
2.1定义
一种基础数据结构，每个元素除了记录自身的值，还会记录下一个元素的内存地址。
2.2优缺点
2.2.1优点
支持快速插入、删除元素。插入、删除元素的操作简单。只需改变特定元素所指向的内存地址，使其指向插入的元素或被删除元素所指向的元素。
2.2.2缺点
不支持快速访问元素，需要从链表的第一个元素，依次访问后续的元素，以找出目标元素。
2.3适用范围
需要快速插入、删除元素，但对查找元素的时效性要求较低的场合。
3.选择排序法
3.1实现原理
遍历其全部元素，找出其最大（最小）的元素。将其从原来的数组中移至新的数据结构中。再从剩余的元素中找出最大（最小）的元素，重复上述移动元素的步骤，直至原来的数据结构中的元素数量为0。
3.2代码实例
#演示选择排序法
import random
#选择数组中最小的元素
def select_smallest(arr):
value=float('inf')
idx=None
for i in range(0,len(arr)):
if value>arr[i]:
value=arr[i]
idx=i
return idx
#主题函数
def selection_sort(arr):
#单独处理arr长度为0或为1的情况
if len(arr)<=1:
return arr
sorted_arr=[]
while arr:
idx=select_smallest(arr)
sorted_arr.append(arr.pop(idx))
return sorted_arr
arr=[random.randint(0,10) for i in range(0,10)]
print('original arr',arr)
print('sorted arr',selection_sort(arr))
