清华数据结构笔记：向量

发表于 | 分类于

向量基础概念

相对于数组固定容量，向量可以进行扩容，向量是以二倍进行扩容

向量实现的详细笔记我会在以后的《STL源码剖析》笔记中记录，该节笔记我打算记录一下向量的二分查找、归并排序等

数组和向量都是连续的内存存储，可以用首地址A + i* s得到下标i对应的元素位置，故下标访问的时间复杂度为O(1)，也称为可以循秩访问，正因为如此有序向量的二分查找速度很快，在后面能看到时间复杂度是O(log n)

由于向量进行了封装，扩容操作后尽管数据区物理地址产生了变化，但是不会出现野指针，这句话很容易理解（扩容后更新向量管理的数组首地址）

所以向量的底层结构可以这样说：可以动态扩容的数组

上面看似废话，但不是废话，可能这句话是废话哈哈！

分摊复杂度：

相对于平均复杂度的概率加权平均，那么分摊复杂度是进行了足够多次的总成本/次数 得到分摊到单次的成本

当然，能进行下标访问是由于重载了[]运算符（此处为C++基础知识）

向量的插入

向量的尾部插入时间复杂度是O(1)

insert插入向量某位置，该位置的后继元素从最后面的元素依次后移一个单元，然后置入新元素，更新size

标准api:

1
2
3
iterator insert (const_iterator position, const value_type& val);
iterator insert (const_iterator position, size_type n, const value_type& val);
template <class InputIterator>iterator insert (const_iterator position, InputIterator first, InputIterator last);

向量的删除

向量的尾部删除时间复杂度是O(1)

后继元素最前面的元素依次前移固定数量单元，更新size

标准api:

1
2
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

无序向量的查找

这里邓老师讲的是，find函数的实现为从后往前查找目标值，这样如果命中的话，得到的是秩最大者

因为向量vector官方标准中未提供find函数，我在进行查找时是通过《algorithm》提供的find函数

1
template <class InputIterator, class T>   InputIterator find (InputIterator first, InputIterator last, const T& val);
1
Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.

翻译过来是从前往后找，与邓老师说的不一致

具体实现依据业务场景需要灵活使用，正如邓老师说的灵活运用

无序向量的去重/唯一化

从前向后遍历，每次在前缀中查找是否重复

判断是否有序可以通过逆序对的数量是否为零来判断

有序向量的去重/唯一化

低效版：可以通过从前向后遍历，每次遇到与前一个元素相同的雷同元素则删除。

​ 因为删除会导致后继元素的整体前移，故最坏情况下，时间复杂度为O(n平方)

高效版：将重复的区间作为一个整体来考虑，成批的删除雷同元素。实现方式即维护双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
// 算法很巧妙
template <typename T>
void vector<T>::uniquify()
{
    Rank i = 0, j = 0;
    while (++j < _size) {
        if (_elem[j] != _elem[i]) {
            _elem[++i] = _elem[j];
        }
        // 会跳过雷同元素
    }
     _size = ++i;
}

二分查找

二分查找版本A

语义：查找目标值，找到目标值返回目标值的秩，找不到则返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Rank BinSearch(T* A, T const& e, Rank lo, Rank hi)
{
    while(lo < hi) {
        Rank mi = (lo + hi) >> 1;
        if (e < A[mi]) {
            hi = mi; // 深入前半段[lo, mi)继续查找
		} else if (e > A[mi]) {
            lo = mi + 1; // 深入后半段[mi + 1, hi)继续查找
        } else {
            return mi;
        }
    }
    return -1;
}

V={2, 3, 5, 7, 11, 13, 17}。V.search(16, 0, 7)需要进行多少次比较？

mi = (0 + 7) >> 1= 3 A[mi] = 7 比较两次后 lo = 3 + 1 = 4; ->[4, 7]查找

mi = (4 +7) >> 1 = 5 A[mi] = 13 比较两次后 lo = 5 + 1 = 6;->[6, 7]查找

mi = (6 +7) >> 1 = 6 A[mi] = 17 比较一次后hi = 6; 跳出循环 故共比较了五次

二分查找版本B

语义：查找目标值，找到目标值返回目标值的秩，找不到则返回-1

上面版本左右分支的比较次数不同

1
2
3
4
5
6
7
8
Rank BinSearch(T* A, T const& e, Rank lo, Rank hi)
{
    while(1 < hi - lo) { //出口时查找区间只剩一个元素
        Rank mi = (lo + hi) >> 1;
        (e < A[mi]) ? hi = mi : lo = mi;
    }
    return (e == A[lo]) ? lo : -1;
}

正因为while循环中的判断条件为是否e < A[mi]，没有判断e是否等于A[lo]，故当查找区间只剩一个元素时退出循环，比较该元素是否与目标元素e相等

二分查找版本C

二分查找A、B版本的语义查找目标值，找到目标值返回目标值的秩，找不到则返回-1

二分查找版本C不同于A、B版本的语义，二分查找版本C返回不大于e的最后一个元素的秩

二分查找版本C是为了能支持插入算法，v.insert(1 + v.search(e), e);

1
2
3
4
5
6
7
8
Rank BinSearch(T* A, T const& e, Rank lo, Rank hi)
{
    while(lo < hi) { //出口时查找区间只剩一个元素
        Rank mi = (lo + hi) >> 1;
        (e < A[mi]) ? hi = mi : lo = mi + 1; // [lo, mi) 或 (mi, hi)
    }
    return --lo;// lo - 1 为不大于e的最后一个元素的秩
}
总结

对于规模为n的向量，二分查找版本A和B的最优时间复杂度分别为：O(1)，O(log n)

对于二分查找版本C，当e<V[mi]不成立时下一步的查找范围是：V(mi, hi)

插值查找

如果有序向量各元素均匀独立分布，即[lo, hi)内各元素应大致按照线性增长

mi - lo /hi - lo ~~ e - A[lo] / A[hi] - A[lo]

通过猜测轴点mi，可以极大提高收敛速度

mi = lo + (hi - lo)*(e - A[lo]) / (A[hi] - A[lo])

例如：在英文字典中

binary大致位于 2/26 处

search大致位于 19/26 处

起泡排序

前面看到有序向量的去重和查找操作相对于无序向量可以快速完成

将无序向量转化为有序向量，起泡排序是一种方式

基础版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename T>
void vector<T>::BubbleSort(Rank lo, Rank hi)
{
	while (lo < hi); // 逐趟做扫描交换，直至全序
	{
		Bubble(lo, hi--);
	}
}

template <typename T>
void vector<T>::Bubble(Rank lo, Rank hi)
{
	while (++lo < hi) {
		if (_elem[lo - 1] > _elem[lo]) {
			sorted = false;
			swap(_elem[lo - 1], _elem[lo]);
		}
	}
}
改进（提前结束）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
void vector<T>::BubbleSort(Rank lo, Rank hi)
{
	while (!(Bubble(lo, hi--)); // 逐趟做扫描交换，直至全序
}

template <typename T>
bool vector<T>::Bubble(Rank lo, Rank hi)
{
	bool sorted = true;
	while (++lo < hi) {
		if (_elem[lo - 1] > _elem[lo]) {
			sorted = false;
			swap(_elem[lo - 1], _elem[lo]);
		}
	}
	return sorted; // 返回有序标志
}
再改进（hi为最后一个逆序对位置）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
void vector<T>::BubbleSort(Rank lo, Rank hi)
{
	while (lo < (hi = bubble(lo, hi)); // 逐趟做扫描交换，直至全序
}

template <typename T>
Rank vector<T>::Bubble(Rank lo, Rank hi)
{
	Rank last = lo;
	while (++lo < hi) {
		if (_elem[lo - 1] > _elem[lo]) {
			last = lo; // 更新最右侧逆序对位置记录
			swap(_elem[lo - 1], _elem[lo]);
		}
	}
	return last; // 返回最有侧逆序对位置
}

题：

一、V={7, 2, 3, 11, 17, 5, 19, 13}，对V进行两次扫描交换后V[6] =？17

2 3 7 11 5 17 13 19

2 3 7 5 11 13 17 19

二、试用以下算法对V={19, 17, 23}排序：

先按个位排序

在上一步基础上，再按十位排序

这个算法的是否正确？

答：以上算法称为“基数排序（radix sort）“，适用于被排序元素可分为若干个域的情况，它的正确性要依赖于对每个域分别排序时的稳定性

归并排序

思想：序列一分为二，子序列递归排序，合并有序子序列

时间复杂度：O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
void vector<T>::MergeSort(Rank lo, Rank hi)
{
    if (hi - lo < 2) {
        return;
    }
	Rank mi = (lo + hi) >> 1;
    MergeSort(lo, mi); // 对前半段排序
    MergeSort(mi, hi); // 对后半段排序
    Merge(lo, mi, hi); // 归并
}

image-20240303132840641

对于规模为n的向量，归并排序的最优、最坏时间复杂度均为：O(nlogn)

因为T(n) = 2T(n/2) + O(n)

位图/Bitmap

通过空间换时间

习题

1.分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，规模为n的向量插入元素的分摊时间复杂度分别为：

答：O(n) O(1)

2.在有序向量V中插入元素e并使之保持有序，下列代码正确的是:

答：V.insert(V.search(e) + 1, e);

3.向量V={2, 3, 5, 7, 11, 13, 17, 19}，在V中使用二分查找版本C查找目标元素16，整个过程中与目标元素发生过比较的元素依次为：

答： 11, 17, 13

4.二分查找“版本C”摘录如下：当数组A中有多个待查找元素e时，函数的返回值为：

答：返回秩最大者

5.V={1, 2, 3, 4, 5, 6, 7}，在V中用Fibonacci查找元素1，被选取为轴点mi的元素依次是：

答：Fib = {0, 1, 1, 2, 3, 5, 8, ……}

[lo, hi) = [0,7): n = 7 = Fib(k)-1 = Fib(6) - 1; k = 6; mid = Fib(6-1) - 1 = 4; 1 < V[mid] = 5;

[lo, hi) = [0, 4): n = 4 = Fib(k)-1 = Fib(5) - 1; k = 5; mid = Fib(5-1) - 1 = 2; 1 < V[mid] = 3;

[lo, hi) = [0, 2): n = 2 = Fib(k)-1 = Fib(4) - 1; k = 4; mid = Fib(4-1) - 1 = 1; 1 < V[mid] = 2;

[lo, hi) = [0, 1): n = 1 = Fib(k)-1 = Fib(3) - 1; k = 3; mid = Fib(3-1) - 1 = 0; V[mid] == 1;

6.对{2, 5, 7}和{3, 11, 13}进行二路归并，执行的元素比较依次是：

答：2 and 3, 5 and 3, 5 and 11, 7and 11

zhangzezhong

参考：清华大学邓俊辉老师数据结构课程第二章向量