选择排序

  • 学习两种最基本的数据结构——数组和链表
  • 学习第一种排序算法

内存的工作原理

需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它们的差别很重要。

数组和链表

需要随机地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素。在链表中,元素并非靠在 一起的,你无法迅速计算出第五个元素的内存地址,而必须先访问第一个元素以获取第二个元素的地址,再访问第二个元素以获取第三个元素的地址,以此类推,直到访问第五个元素。

需要在中间插入元素时,数组和链表哪个更好呢?使用链表时,插入元素很简单,只需修改它前面的那个元素指向的地址。而使用数组时,则必须将后面的元素都向后移。如果没有足够的空间,可能还得将整个数组复制到其他地方!因此,当需要在中间插入元素时,链表是更好的选择。

删除元素呢?链表也是更好的选择,因为只需修改前一个元素指向的地址即可。而使用数组时,删除元素后,必须将后面的元素都向前移。

20220615173051

数组和链表哪个用得更多呢?显然要看情况。但数组用得很多,因为它支持随机访问。有两种访问方式:随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问:要读取链表的第十个元素,得先读取前九个元素,并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快,这是因为它们支持随机访问。很多情况都要求能够随机访问,因此数组用得很多。数组和链表还被用来实现其他数据结构,

选择排序

假设你的计算机存储了很多乐曲。对于每个乐队,你都记录了其作品被播放的次数。你要将这个列表按播放次数从多到少的顺序排列,从而将你喜欢的乐队排序。

20220615173442

要找出播放次数最多的乐队,必须检查列表中的每个元素。正如你刚才看到的,这需要的时间为O(n)。因此对于这种时间为O(n)的操作,你需要执行n次。需要的总时间为 \(O(n × n)\),即\(O(n_2)\)

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

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

小结

  • 计算机内存犹如一大堆抽屉。
  • 需要存储多个元素时,可使用数组或链表。
  • 数组的元素都在一起。
  • 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。
  • 数组的读取速度很快。
  • 链表的插入和删除速度很快。
  • 在同一个数组中,所有元素的类型都必须相同(都为int、double等)。

如果你在哪儿卡住了,可以到这里查看源码。