返回：0300 数据结构总目录 · 上一章：0301 Chap1 绪论与算法分析 · 下一章：0303 Chap3 列表

1、学习目标

向量可以看成“可扩展数组”。它保留数组的随机访问优势，又通过扩容机制支持动态增长。本章重点不是会用 std::vector，而是理解背后的 ADT、容量管理、查找、去重和排序。

模块 要掌握的内容
ADT 规模、容量、秩、访问、插入、删除
扩容 加倍扩容、装填因子、分摊复杂度
无序向量 顺序查找、插入、删除、唯一化
有序向量 去重、二分查找、Fibonacci 查找、插值查找
排序 冒泡排序、归并排序

2、资料范围

PDF 课件 内容
02.Vector.A.Interface_Implementation.pdf 向量接口与实现
02.Vector.B.extendable_vector.pdf 可扩展向量
02.Vector.C.unsorted_Vector.pdf 无序向量
02.Vector.D1-D5 有序向量、唯一化和查找
02.Vector.E.Bubblesort.pdf 冒泡排序
02.Vector.F.Mergesort.pdf 归并排序

3、向量 ADT

向量中每个元素都有一个秩 rank，取值范围是 [0, size)。

操作 含义 复杂度
size() 返回元素数 O(1)
get(r) 按秩访问 O(1)
put(r, e) 替换元素 O(1)
insert(r, e) 在秩 r 前插入 O(n-r)
remove(r) 删除秩 r 元素 O(n-r)
find(e) 无序查找 O(n)
search(e) 有序查找 O(log n) 或更好条件下更优

核心矛盾：

1
随机访问很快，但中间插入/删除需要移动元素。

4、动态扩容

向量通常维护两个量：

1
2
3
int _size;      // 实际元素数
int _capacity;  // 底层数组容量
T*  _elem;      // 数据区

扩容策略：

1
2
3
4
5
6
if (_size < _capacity) return;
_capacity = max(DEFAULT_CAPACITY, _capacity * 2);
T* old = _elem;
_elem = new T[_capacity];
for (int i = 0; i < _size; ++i) _elem[i] = old[i];
delete[] old;

单次扩容是 O(n)，但如果采用加倍扩容，连续 n 次 push_back 的总移动次数是线性级，平均到每次插入就是分摊 O(1)。

不要用每次只扩容一个位置的策略。那会让连续插入退化成 1+2+...+n = O(n^2)。

5、无序向量

5.1 顺序查找

无序向量没有结构信息，只能从后往前或从前往后逐个比较。

1
2
3
4
int find(const T& e, int lo, int hi) {
    while ((lo < hi--) && e != _elem[hi]) {}
    return hi; // 失败时 hi < lo
}

从后往前查找的好处是：如果找到，返回最后出现的位置；如果后面要做去重，删除后面的重复元素更方便。

5.2 插入和删除

插入需要把 [r, size) 整体后移：

1
2
3
4
5
6
7
int insert(int r, const T& e) {
    expand();
    for (int i = _size; r < i; --i) _elem[i] = _elem[i - 1];
    _elem[r] = e;
    ++_size;
    return r;
}

删除区间 [lo, hi)：

1
2
3
4
5
6
7
int remove(int lo, int hi) {
    if (lo == hi) return 0;
    while (hi < _size) _elem[lo++] = _elem[hi++];
    _size = lo;
    shrink();
    return hi - lo;
}

5.3 无序唯一化

低效版：

1
2
3
4
5
6
7
8
9
int deduplicate() {
    int oldSize = _size;
    int i = 1;
    while (i < _size) {
        if (find(_elem[i], 0, i) < 0) ++i;
        else remove(i);
    }
    return oldSize - _size;
}

每个元素都可能向前查找，删除还可能移动元素，最坏 O(n^2)。

6、有序向量

有序向量的核心收益是查找和去重更快。

6.1 有序唯一化

有序向量重复元素必然相邻，所以可以用双指针线性压缩：

1
2
3
4
5
6
7
8
9
10
int uniquify() {
    if (_size < 2) return 0;
    int i = 0, j = 0;
    while (++j < _size) {
        if (_elem[i] != _elem[j]) _elem[++i] = _elem[j];
    }
    _size = ++i;
    shrink();
    return j - i;
}

复杂度 O(n)。

6.2 二分查找

语义最好统一成：

1
在有序区间 [lo, hi) 中，返回不大于 e 的最后一个元素秩；若都大于 e，返回 lo-1。

这样插入位置就是 search(e) + 1。

1
2
3
4
5
6
7
8
int search(const T& e, int lo, int hi) {
    while (lo < hi) {
        int mi = (lo + hi) >> 1;
        if (e < _elem[mi]) hi = mi;
        else lo = mi + 1;
    }
    return --lo;
}

这种写法能自然处理重复元素，返回最后一个 <= e 的位置。

7、向量排序

7.1 冒泡排序

冒泡排序不断扫描相邻逆序对，把较大元素推向末端。

1
2
3
4
5
6
7
8
9
10
bool bubble(int lo, int hi) {
    bool sorted = true;
    while (++lo < hi) {
        if (_elem[lo - 1] > _elem[lo]) {
            swap(_elem[lo - 1], _elem[lo]);
            sorted = false;
        }
    }
    return sorted;
}

复杂度：

情况 复杂度
最好 O(n)
最坏 O(n^2)
稳定性 稳定

7.2 归并排序

归并排序采用分而治之：

1
先递归排左半和右半，再把两个有序区间合并。
1
2
3
4
5
6
7
void mergeSort(int lo, int hi) {
    if (hi - lo < 2) return;
    int mi = (lo + hi) >> 1;
    mergeSort(lo, mi);
    mergeSort(mi, hi);
    merge(lo, mi, hi);
}

复杂度稳定为 O(n log n)，需要 O(n) 辅助空间，适合强调稳定性和可预测性能的场景。

8、复杂度汇总

操作 无序向量 有序向量
按秩访问 O(1) O(1)
查找 O(n) O(log n)
插入 O(n) O(n)
删除 O(n) O(n)
去重 O(n^2) O(n)

9、易错点

易错点 修正
把向量插入当成 O(1) 只有尾部插入分摊 O(1)，中间插入要移动元素
二分边界混乱 统一使用 [lo, hi) 半开区间
忘记重复元素语义 明确返回首个、最后一个，还是任意一个匹配位置
扩容后旧指针仍使用 扩容会换底层数组，旧地址可能失效

10、复盘清单

检查项 状态
能写出向量 insert/remove 的移动过程 待复盘
能解释加倍扩容的分摊 O(1) 待复盘
能区分无序去重和有序去重复杂度 待复盘
能写出返回最后一个 <= e 的二分查找 待复盘
能比较冒泡排序和归并排序 待复盘