算法图解-选择排序

1. 链表
- 链表中的元素可存储在内存的任何地方。而数组的元素都在一起
- 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一
起。

链表元素在内存中的存储.png
2. 链表和数组的区别
- 需要同时读取所有元素时，链表的效率很高
- 需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素

3. 下图是常见数组和链表操作的运行时间

image.png

4. 选择排序

#  将数组元素按从小到大的顺序排列。先编写一个用于找出数组中最小元素的函数
def findSmallest(arr):
  smallest = arr[0] # 存储最小的值
  smallest_index = 0 # 存储最小元素的索引
  for i in range(1, len(arr)):
      if arr[i] < smallest:
          smallest = arr[i]
          smallest_index = i
  return smallest_index

# 利用findSmallest函数实现选择排序算法
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # 找出数组中最小的元素,并将其加入到新数组中
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr
print(selectionSort([5, 3, 6, 2, 10]))