《算法图解》学习记录_chapter2（选择排序）

Chapter2 选择排序

本章内容：
✔️学习两种最基本的数据结构——数组和链表（ref- C语言）；
✔️学习第一种排序算法——选择排序

1. 内存的工作原理：

计算机内存的工作原理：计算机就像是很多抽屉的集合体，每个抽屉都有地址。

需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。

2. 基本数据结构：数组和链表

问题：假设你要编写一个管理待办事项的应用程序，为此需要将这些待办事项存储在内存中。应使用数组还是链表呢?

- 数组：

我们先将待办事项存储在数组中。使用数组意味着所有待办事项在内存中都是相连的(紧靠在一起的)。

现在假设你要添加第四个待办事项，但后面的那个抽屉放着别人的东西！在这种情况下，你需要请求计算机重新分配一块可容纳4个待办事项的内存，再将所有待办事项都移到那里。

在数组中添加新元素也可能很麻烦。如果没有了空间，就得移到内存的其他地方，因此添加新元素的速度会很慢。
一种解决之道是“预留座位”:即便当前只有3个待办事项，也请计算机提供10个位置，以防需要添加待办事项。

这种方式存在如下两个缺点：
・你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不了。
・待办事项超过10个后，你还得转移。

对于这种问题，可使用链表来解决。

- 链表：

如下图所示，链表中的元素可存储在内存的任何地方。

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

在链表中添加元素很容易：只需将其放入内存，并将其地址存储到前一个元素中。使用链表时不需要移动元素，只要有足够的内存空间，就能为链表分配内存。

链表的优势在插入元素方面，那数组的优势又是什么呢?

在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3 的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高:你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。
数组则不同：你知道其中每个元素的地址。例如，假设有一个数组，它包含五个元素，起始地址为00，那么元素#5的地址是多少呢?只需执行简单的数学运算就知道元素#5的地址为04。**需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。**在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问第五个元素。
总结一下就是：数组的读取速度快， 而插入速度慢；链表的读取速度慢，而插入速度快。

注意：
数组的元素带编号，编号从0而不是1开始。几乎所有的编程语言都从0开始对数组元素进行编号。元素的位置称为索引。因此，不说“元素20的位置为1”，而说“元素20位于索引1处”。

- 在中间插入：

问题：假设你要让待办事项按日期排列。之前，你在清单末尾添加了待办事项。但现在你要根据新增待办事项的日期将其插入到正确的位置，数组和链表哪个更好呢？

需要在中间插入元素时，使用链表时插入元素很简单：只需修改它前面的那个元素指向的地址。

而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间（如
下图所示），可能还得将整个数组复制到其他地方!

• Q：假设要在数组开头插入一个元素，你将如何做？这需要多长时间?如果在数组末尾插入一个元素又如何呢？想象插入时内存空间不够的情况。

- 删除：

Q：如果你要删除元素，数组和链表哪个更好呢？

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

不同于插入，删除元素总能成功。如果内存中没有足够的空间，插入操作可能失败，但在任何情况下都能够将元素删除。

常见的数组和链表操作的运行时间：

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

（需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。通常我 们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O(1)。）

• Q：那什么情况下不能够立即访问要删除的元素呢？

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

• Q：练习2.5

3. 选择排序：

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

算法：一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。继续这样做，你将得到一个有序列表。

反复，直到得到最终结果：

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

因此，需要的总时间为 O(n × n)，即O(n^2)。

• Q：随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一 个。既然如此，运行时间怎么还是O(n^2)呢?这个问题问得好，这与大O表示法中的常数相关。 第4章将详细解释

- Python实现：

# selection sort algorithm

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_index = findSmallest(arr)
		newArr.append(arr.pop(smallest_index))
	return newArr

arr = [5,3,6,2,10]

print(selectionSort(arr))

(试着编写出对乐队进行排序的代码)

@ 小结：

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