• 计算机内存犹如堆叠的抽屉
  • 存储多个元素的结构：数组和链表
    • 数组：元素连续排放在一起。读取速度快（索引读取）
    • 链表：每个存储单元中含有指针指向下一个元素地址，因此可分开存放（插入和删除速度快，不需要移动其他元素位置，仅需要修改指针）
  • 在同一个数组（Array）中，所有元素的类型必须相同（int、double等）

选择排序

举例：根据你喜爱音乐的播放次数，排序歌曲

  • 新建一个表，记录已排序的结构
  • 从现有表中找出播放次数最多的歌曲，放入新表
  • 第二步找出第二多的歌曲放入新表
  • 依次进行，知道结束，得到已排序的新表

时间复杂度：O(n*n)

  1. def find_smallest(arr):
  2.     smallest = arr[0]
  3.     smallest_index = 0
  4.     for i in range(1, len(arr)):
  5.         if arr[i] < smallest:
  6.             smallest = arr[i]
  7.             smallest_index = i
  8.     return smallest_index
  10. def selection_sort(arr):
  11.     new_arr = []
  12.     for i in range(len(arr)):
  13.         smallest_index = arr.pop(find_smallest(arr))
  14.         new_arr.append(smallest_index)
  15.     return new_arr