【学习】《算法图解》第二章学习笔记：数组、链表与选择排序

前言

继第一章介绍了算法的基本概念和二分查找后，《算法图解》第二章将带领我们进一步探索数据组织的方式，引入了两种基础且重要的数据结构：数组（Array）和链表（Linked List）。理解它们的特性和区别对于后续学习更复杂的算法至关重要。此外，本章还介绍了第一个排序算法——选择排序（Selection Sort）。笔者将结合书中内容和个人理解，对本章知识点进行梳理。

一、内存工作原理简介

在探讨数组和链表之前，我们有必要简单了解一下计算机是如何存储数据的。想象一下，计算机的内存就像一个巨大的柜子，里面有很多抽屉。每个抽屉都有编号（内存地址），可以存放数据。

• 存储数据：当程序需要存储数据时，会向操作系统请求一块内存空间。操作系统找到合适的”抽屉”并将数据放进去。
• 读取数据：当程序需要读取数据时，会根据内存地址找到对应的”抽屉”，取出里面的数据。

这种机制是数组和链表实现的基础。

二、数组（Arrays）

数组是一种将相同类型的元素存储在连续内存空间中的数据结构。这意味着数组中的所有元素都是紧挨着存放的。

（一）数组的特点

1. 连续存储：这是数组最核心的特点。由于元素是连续存储的，我们可以通过索引快速访问任何元素。
2. 相同类型：数组通常要求存储的元素类型一致。
3. 固定大小：在很多语言中，数组一旦创建，其大小就固定了，不易动态调整（动态数组除外，但其调整大小通常涉及额外开销）。

（二）数组的优缺点

优点：

• 读取速度快：由于元素在内存中是连续存储的，可以通过索引直接计算出元素的内存地址，因此读取操作非常高效，时间复杂度为 O(1)。例如，如果知道数组的起始地址和元素大小，那么第 i 个元素的地址就是 起始地址 + i * 元素大小。

缺点：

• 插入和删除慢：
  • 插入：如果在数组中间插入一个元素，需要将该位置之后的所有元素向后移动一位，以腾出空间。最坏情况下（在数组开头插入），需要移动所有元素，时间复杂度为 O(n)。
  • 删除：类似地，如果在数组中间删除一个元素，需要将该位置之后的所有元素向前移动一位，以填补空缺。最坏情况下（删除数组开头的元素），时间复杂度也为 O(n)。
• 大小固定：如前所述，传统数组大小固定，在需要动态增删元素的场景下可能不够灵活。

（三）Python中的列表（List）作为数组的例子

Python 的列表（List）虽然是动态数组，但在很多方面展现了数组的特性，尤其是在通过索引访问元素时。

# Python 列表示例
my_list = [10, 20, 30, 40, 50]

# 读取元素 (O(1))
print(my_list[2])  # 输出: 30

# 插入元素 (平均 O(n))
my_list.insert(1, 15) # 在索引1处插入15
print(my_list) # 输出: [10, 15, 20, 30, 40, 50]

# 删除元素 (平均 O(n))
my_list.pop(3) # 删除索引3处的元素 (原30，现20之后是30)
print(my_list) # 输出: [10, 15, 20, 40, 50]

三、链表（Linked Lists）

与数组不同，链表中的元素在内存中不必连续存储。每个链表元素（称为节点 Node）包含两部分：

1. 数据（Data）：存储元素本身的值。
2. 指针（Pointer/Next）：存储下一个节点的内存地址。

链表的第一个节点称为头节点（Head），最后一个节点的指针通常指向空（None 或 NULL）。

（一）链表的特点

1. 非连续存储：元素可以在内存中分散存储，通过指针连接。
2. 动态大小：链表的大小可以很容易地动态改变，插入和删除节点相对灵活。

（二）链表的优缺点

优点：

• 插入和删除快：
  • 插入：只需要修改相邻节点的指针即可，时间复杂度为 O(1)（如果已知要插入位置的前一个节点）。
  • 删除：同样只需要修改相邻节点的指针，时间复杂度为 O(1)（如果已知要删除节点的前一个节点）。
• 大小灵活：可以根据需要动态添加或删除元素。

缺点：

• 读取速度慢：由于元素在内存中不是连续存储的，不能像数组那样通过索引直接计算地址。要访问链表中的某个元素（例如第 i 个元素），必须从头节点开始，沿着指针逐个遍历，直到找到目标元素。因此，读取操作的时间复杂度为 O(n)。

（三）简单链表示例（概念）

由于 Python 没有内置的纯粹链表结构（collections.deque 更像是双向链表），这里用一个简单的类来示意其概念：

class Node:
    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 指向下一个节点的指针

# 创建节点
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

# 连接节点形成链表: 10 -> 20 -> 30 -> None
node1.next = node2
node2.next = node3

# 遍历链表
current = node1
while current:
    print(current.data)
    current = current.next
# 输出:
# 10
# 20
# 30

四、数组 vs. 链表

特性	数组 (Array)	链表 (Linked List)
读取	O(1) (快)	O(n) (慢)
插入	O(n) (慢)	O(1) (快，如果知道前驱节点)
删除	O(n) (慢)	O(1) (快，如果知道前驱节点)
内存分配	连续空间	可不连续空间
大小	通常固定 (或动态调整有开销)	动态灵活

选择建议：

• 如果你需要频繁地随机访问元素，且集合大小相对固定，数组可能是更好的选择。 例如，存储一个班级所有学生按学号排列的成绩单。
• 如果你需要频繁地插入和删除元素，且对读取速度要求不高，链表可能更合适。 例如，实现一个任务队列，任务会频繁地加入和移除。

《算法图解》中提到一个经验法则：数组的读取速度很快，链表的插入和删除速度很快。

五、选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理如下：

1. 首先，在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
2. 然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
3. 以此类推，直到所有元素均排序完毕。

（一）算法步骤

假设我们要对一个列表进行升序排序：

1. 遍历列表，找到最小的元素。
2. 将这个最小的元素与列表的第一个元素交换位置。
3. 现在列表的第一个元素就是有序的了。接下来，从列表的第二个元素开始，重复上述过程，找到剩余元素中最小的，并与第二个元素交换。
4. 持续这个过程，每次都从当前未排序的部分找到最小元素，并将其放到已排序部分的末尾。

（二）Python代码示例

《算法图解》中提供的选择排序 Python 代码如下：

# 找出数组中最小元素的函数
def find_smallest(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 selection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest_index = find_smallest(arr) # 找出数组中最小的元素，并将其加入到新数组中
        new_arr.append(arr.pop(smallest_index))
    return new_arr

# 测试
my_array = [5, 3, 6, 2, 10]
print(f"Original array: {my_array}")
sorted_array = selection_sort(my_array)
print(f"Sorted array: {sorted_array}")
# Output:
# Original array: [5, 3, 6, 2, 10]
# Sorted array: [2, 3, 5, 6, 10]

这个实现通过 arr.pop(smallest_index) 来获取最小元素并从原数组中移除它，这在 Python 中是可以的，但会改变原始列表。另一种常见的实现方式是原地排序，即不创建新列表，而是在原列表上进行元素交换。

（三）运行时间

选择排序的运行时间很容易分析。对于一个包含 n 个元素的列表：

1. 第一次查找最小元素，需要比较 n 次。
2. 第二次查找最小元素（在剩下的 n-1 个元素中），需要比较 n-1 次。
3. …
4. 最后一次，需要比较 1 次。

总的比较次数大约是 ( n + (n-1) + … + 1 = n * (n+1) / 2 )，也就是 ( O(n^2/2 + n/2) )。
根据大O表示法的规则，我们忽略常数和低阶项，因此选择排序的时间复杂度为 **O(n²)**。

这意味着当列表长度增加时，选择排序所需的时间会急剧增加。例如，如果列表长度翻倍，排序时间大约会变成原来的四倍。对于大规模数据的排序，选择排序并不是一个高效的选择，但它因为简单易懂，常作为入门排序算法来学习。

六、总结

《算法图解》第二章为我们介绍了两种基础数据结构——数组和链表，它们是构建更复杂数据结构和算法的基石。通过对比它们的特性、优缺点以及操作的时间复杂度，我们可以根据实际需求选择合适的数据结构。此外，本章介绍的选择排序算法，虽然效率不高（O(n²)），但其思想简单直观，有助于理解排序的基本概念。理解这些基础知识对于后续学习更高级的算法至关重要。

七、参考资料

• 《算法图解》 （Grokking Algorithms） by Aditya Y. Bhargava
• 《算法图解》第二章 - 选择排序 - CSDN博客
• 《算法图解》学习笔记（二）：选择排序 - 博客园
• 《算法图解》第二章–选择排序 - 知乎