ch2 向量¶

1. 抽象数据类型¶

【抽象数据类型】数据模型 + 定义在该模型上的一组操作。

是一种抽象定义。
仅考虑外部的逻辑特性，不考虑时间复杂度。
仅考虑操作和语义，不涉及数据的存储方式。

【数据结构】基于某种特定语言，实现 \(\tt ADT\) 的一整套算法。

是具体实现，而且可以有多种不同的实现。
要考虑内部的表示与实现，与复杂度密切相关。
是一个完整的算法，要考虑数据的具体存储机制。

在数据结构的具体实现与实际应用之间，\(\tt ADT\) 就分工与接口制定了统一的规范

实现：高效兑现数据结构的 \(\tt ADT\) 接口操作。
应用：便捷地通过操作接口使用数据结构。

按照 \(\tt ADT\) 规范，高层算法设计者可与底层数据结构实现者高效地分工协作，不同地算法与数据结构可以便捷组合借用，每种操作接口只需统一地实现一次，代码篇幅缩短，安全性加强，软件复用度提高。

【向量】是数组地抽象与泛化，由一组元素按线性次序封装而成，各元素与 \([0,n)\) 内的秩一一对应。

2. 可扩充向量¶

【静态空间管理】容量 \(\_capacity\) 固定，存在明显不足

上溢：\(\_elem[]\) 不足以存放所有元素
下溢：\(\_elem[]\) 中的元素寥寥无几
装填因子：\(\lambda = \_size / \_capacity << 50\%\)

【动态空间管理】在即将上溢时，适当扩大内部数组的容量。扩容算法一般采用倍增策略。

【平均分析与分摊分析】

平均：根据各种操作出现概率的分布，将对应的成本加权平均。各种可能的操作，作为独立事件分别考查，割裂了操作之间的相关性和连贯性。
分摊：连续实施的足够多次操作，所需总体成本摊还至单次操作。从实际可行的角度，对一系列操作做整体的考量，更加忠实地刻画了可能出现地操作序列。

3. 有序向量¶

在有序序列中，任何一对相邻元素必顺序，因此，相邻逆序对的数目，可在一定程度上度量向量的紊乱程度。

【二分查找】以任一元素 \(x = [mi]\) 为界，都可将待查找区间 \([lo, hi)\) 分为三部分 \([lo, mi)\le [mi]\le (mi, hi)\)，因此只需将目标元素 \(e\) 与 \(x\) 做一次比较，即可分为三种情况进一步处理：

\(e<x\)：则 \(e\) 若存在，必属于左侧子区间，故可减除 \([mi, hi)\) 并递归深入 \([li, mi)\)
\(x < e\)：则 \(e\) 若存在，必属于右侧子区间，亦可减除 \([lo, mi]\) 并递归深入 \((mi, hi)\)
\(e = x\)：已在此处命中，可立即返回

若轴点 \(mi\) 取中点，则每经过至多两次比较，或者能够命中，或者将问题规模缩减一半。查找成功或失败的平均查找长度均为 \(1.5\log n\)，因为转向左、右分支前的关键码比较次数不等，而递归深度却相同。

【Fibonacci 查找】通过递归深度的不均衡对转向成本的不均衡做补偿，平均查找长度可以进一步缩短。

【通用策略】在任何区间 \([0,n)\) 内，总是选取 \([\lambda n]\) 作为轴点，\(0 \le \lambda < 1\)，比如二分查找对应于 \(\lambda = 0.5\)，Fibonacci 查找对应于 \(\lambda = \phi = 0.618\)。这类查找算法的渐进复杂度为 \(\alpha(\lambda)\log_2 n = \cal{O}(\log n)\)。当 \(\lambda = \phi = (\sqrt{5} - 1)/2\) 时，\(\alpha(\lambda) = 1.44\) 达到最小。

【插值查找】根据大数定律（越长的序列，元素的分布越有规律），\([lo, hi]\) 内各元素应大致呈线性趋势增长，\((mi-lo)/(hi-lo) \approx (e-A[lo])/(A[hi]-A[lo])\)。因此通过猜测轴点 \(mi\)，可以极大地提高收敛速度 \(mi\approx lo + (hi-lo)(e-A[lo])/(A[hi]-A[lo])\)。最坏情况下渐进时间复杂度为 \(\cal{O}(n)\)，平均情况下渐进时间复杂度为 \(\cal{O}(\log \log n)\)，即每经过一次比较，待查找区间宽度由 \(n\) 缩至 \(\sqrt{n}\)，有效字长 \(\log n\) 减半。

插值查找在字长意义上是折半查找；二分查找在字长意义上是顺序查找。

4. 冒泡排序¶

【基本思想】依次比较每一对相邻元素，如有必要，交换之，直至某趟扫描后，确认相邻元素均已顺序。

C++

// 基本版：[L, R)
void bubbleSort(int L, int R) {
    while (L < --R)
        for (int i = L; i < R; i++)
            if (elem[i] > elem[i+1])
                swap(elem[i], elem[i+1]);
}

C++

// 提前终止版：[L, R)
void bubbleSort(int L, int R) {
    for (bool sorted = false; sorted = !sorted; R--)
        for (int i = L; i < R - 1; i++)
            if (elem[i] > elem[i+1])
                swap(elem[i], elem[i+1]), sorted = false;
}

C++

// 跳跃版：[L, R)
void bubbleSort(int L, int R) {
    for (int last; L < R; R = last)
        for (int i = last = L; i < R - 1; i++)
            if (elem[i] > elem[i+1])
                swap(elem[i], elem[i+1]), last = i + 1;
}

【稳定性】相等的元素在输入、输出序列中的相对次序，若保持不变，则称该排序算法是稳定的。