ch3 链表

1. 循秩访问

根据是否修改数据结构，所有操作大致分为两类

• 静态：仅读取，数据结构的内容及组成一般不变
• 动态：需写入，数据结构的局部或整体将改变

与操作方式相对应地，数据元素的存储与组织方式也分为两种

• 静态：数据空间整体创建或销毁。数据元素的物理次序与其逻辑次序严格一致，可支持高效的静态操作。
• 动态：为各数据元素动态地分配和回收地物理空间。相邻元素记录彼此的物理地址，在逻辑上形成一个整体，可支持高效的动态操作。

【链表】采用动态储存策略的典型结构。其中的元素称为节点，通过指针或引用彼此连接，在逻辑上构成一个线性序列。相邻节点彼此互称前驱或后继，没有前驱 / 后继的节点称作首 / 末节点。

• 链表中各元素的物理地址将不再决定于逻辑次序，动态操作可以在局部完成。
• 循秩访问：利用节点之间的相互引用，找到特定的节点。

2. 选择排序

冒泡排序扫描交换的实质效果是通过比较找到当前的最大元素 \(M\)，并通过交换使之就位。事实上，经过 \(\cal{O}(n)\) 次比较确定 \(M\) 之后，仅需一次交换足矣。

【选择排序】有多个元素同时命中时，约定返回其中最靠后者，若采用平移法，可保证稳定性；若采用交换法，无法保证稳定性。

• 时间复杂度与冒泡排序一致，均为 \(\cal O(n^2)\)，但是元素的移动操作远远少于冒泡排序。

3. 插入排序

【插入排序】始终将序列视作两部分

• 前缀 \(S[0,r)\)：有序子序列
• 后缀 \(U[r,n)\)：待排子序列

初始时 \(|S| = r = 0\)，反复地针对 \(e = A[r]\)，在 \(S\) 中查找适当位置插入 \(e\)，\(r++\)。

插入排序是一个允许在线处理的排序算法。