《算法图解》第二章笔记与课后练习

软件环境：Python 3.7.0b4

一、选择排序

# 找出数组中的最小元素
def findSmallest(arr):
  # 存储最小的值
  smallest = arr[0]
  # 存储最小元素的索引
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest_index = i
      smallest = arr[i]      
  return smallest_index

# 排序算法
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # 找出数组中最小的元素，并将其加入到新的数组中
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

二、课后练习

答案（如果有更好的欢迎评论或私信~）

2.1：每天都在列表中添加支出项，但每月只读取支出一次。而数组的读取速度很快，但插入速度慢；链表的读取速度慢，但插入速度快。因为我们执行的插入操作比读取操作多，因此使用链表合适。

2.2：经常要执行插入操作——服务员添加点菜单，而链表的插入速度很快；而且不需要执行查找和随机访问操作（这是数组擅长的），因为厨师总是从队列中取出第一个点菜单。综上所述，使用链表合适。

2.3：有序数组。数组让你能够随机访问从而立即获取数组中间的元素，而使用链表无法这样操作。要获取链表中间的元素，就必须从第一个元素开始，沿链接逐渐找到这个元素。

2.4：数组的插入速度很慢。另外如果要使用二分查找算法来查找用户名，数组必须是有序的，因此每次插入用户名后，都必须对数组进行排序。

2.5：查找时，其速度比数组慢，但比链表快；而在插入时，其速度比数组快，但与链表相当。因此，除了查找速度比数组慢，其他方面并不比链表慢。

三、小结

• 需要存储多个元素时，可使用数组或链表。
• 数组的元素都是连在一起的，就像一节节车厢。
• 链表的元素是分散开的，其中每个元素都存储了下一个元素的地址。
• 数组的读取速度很快。
• 链表的插入和删除的速度很快。
• 在同一个数组中，所有元素的类型都必须相同（都为int、double等）。