本文共 11391 字，大约阅读时间需要 37 分钟。
第二章：向量
抽象数据类型ADT
ADT = 数据模型 + 操作
数据结构 = 用某种语言实现ADT的一整套算法。
vector-寻秩访问，元素与秩一一对应
ADT接口：
注：disordered（）函数返回向量中紧邻逆序对的数目。
模板类
可扩充向量：
静态空间管理：向量容量从最开始就固定不变，存在很大的不足。
空间效率：
上溢（overflow）：_elem[]不足以存放所有的元素，尽管此时系统仍然有足够的空间。
下溢（underflow）：_elem[]中的元素寥寥无几。
装填因子：向量size/总容量。
总而言之，上溢是vector原本分配的空间不足，而下溢则是元素填充率太低。
动态空间管理：在即将发生上溢时，适当扩大内部数组的容量。
扩容算法：
templatevoid Vector ::expand() { //向量空间不足时扩容 if ( _size < _capacity ) return; //尚未满员时，不必扩容 if ( _capacity < DEFAULT_CAPACITY ) _capacity = DEFAULT_CAPACITY; //不低于最小容量 T* oldElem = _elem; _elem = new T[_capacity <<= 1]; //容量加倍 for ( int i = 0; i < _size; i++ ) _elem[i] = oldElem[i]; //复制原向量内容（T为基本类型，或已重载赋值操作符'='） delete [] oldElem; //释放原空间}
可见向量的扩容算法主要做了两件事，其一是重新为vector分配内存，新的容量为原来容量的两倍；其二是将原来向量的内容拷贝到新的内存空间中。
这里的实现细节是先定义一个副本保存原向量数组的首地址，然后将给向量封装类中的_elem重新分配内存，分配好了将副本中的内容拷贝到新的内存空间，释放掉副本内存，这里_elem将一直指向vector的首地址，不会出现野指针。
还需要注意的是分配内存的语句默认为时间复杂度为常数的，这里扩容算法的复杂度消耗在于向量内容的拷贝上，故总的时间复杂度是O(n)，n为向量元素的个数。
如果不采用这种加倍策略进行扩容，只是简单的线性扩容的话，设每次扩容的容量为I，连续插入n = mI个元素，则在第1，I+1,2I+1，…次插入时，都需要扩容，时间成本分别为0，I，2I，…（m-1）I，算术级数与末项平方同阶，故总的耗时为O（m^2）,即O(n^2).每次扩容的分摊成本为O(n).
而使用倍增策略的话，连续插入n = 2^m个元素，在第1,2,4，…，2^m次插入时需要扩容，几何级数与末项同阶，即总的时间成本为O(n),每次扩容的分摊成本只需O（1）。
平均复杂度与分摊复杂度对比
平均复杂度：将各种操作作为独立的事件，求的的概率的加权平均，割裂了各个操作的相关性和连贯性，不能准确地反映算法的真实性能。
分摊复杂度：对数据结构连续的进行足够多次操作，所需的总体成本分摊至单次操作，更加准确。
无序向量：
元素访问：重载了[]。
templateT & vector ::operator[](Rank r) const{retrun _elem[r];}
并且，由于返回的是引用类型，故v[]即可作为左值，也可作为右值。
插入：
template//将e作为秩为r元素插入Rank Vector ::insert ( Rank r, T const& e ) { //assert: 0 <= r <= size expand(); //若有必要，扩容 for ( int i = _size; i > r; i-- ) _elem[i] = _elem[i-1]; //自后向前，后继元素顺次后移一个单元 _elem[r] = e; _size++; //置入新元素并更新容量 return r; //返回秩}
注意：这里元素的插入，需要将待插入位置后面的元素一个个自后向前的右移一位，方向不能颠倒，否则会造成元素的覆盖。
区间删除：
templateint Vector ::remove ( Rank lo, Rank hi ) { //删除区间[lo, hi) if ( lo == hi ) return 0; //出于效率考虑，单独处理退化情况，比如remove(0, 0) while ( hi < _size ) _elem[lo++] = _elem[hi++]; //[hi, _size)顺次前移hi - lo个单元 _size = lo; //更新规模，直接丢弃尾部[lo, _size = hi)区间 shrink(); //若有必要，则缩容 return hi - lo; //返回被删除元素的数目}
删除操作只需要将待删除区间元素后面所有的元素一个个的前移hi-lo个单元即可，这里移动的顺序同样不能颠倒，必须是自前向后一个个前移，否则还是会造成元素的覆盖。
比如1 2 3 4 5，如果删除2，从前向后前移得到1 3 4 5，而从后向前移动则会得到1 5 5 5，完全覆盖了不该删除的元素。
单元素删除：
templateT Vector ::remove ( Rank r ) { //删除向量中秩为r的元素，0 <= r < size T e = _elem[r]; //备份被删除元素 remove ( r, r + 1 ); //调用区间删除算法，等效于对区间[r, r + 1)的删除 return e; //返回被删除元素}
直接调用区间删除的接口，就能实现单元素删除的功能。为什么不能反过来调用单元素删除的算法去实现区间删除的算法呢？因为区间删除的时间消耗在元素的移动上，把n的元素移动n个距离，n次移动，每次移动n单元距离，时间复杂度是O（n）；如果反复的调用单元素删除的接口则需要先进行n次移动，将n个元素移动一个单元，然后还要重复n次，总的时间复杂度是O(n^2)级别的，这就类似于一个三级的台阶，区间删除是一步跨上台阶，而单元素删除是一步一级台阶，三步才能走上台阶。
查找：
template//无序向量的顺序查找：返回最后一个元素e的位置；失败时，返回lo - 1Rank Vector ::find ( T const& e, Rank lo, Rank hi ) const { //assert: 0 <= lo < hi <= _size while ( ( lo < hi-- ) && ( e != _elem[hi] ) ); //从后向前，顺序查找 return hi; //若hi < lo，则意味着失败；否则hi即命中元素的秩}
输入敏感算法：算法消耗的时间与输入序列的性质有关。比如find函数最好情况下复杂度为O(1)，而最坏情况下时间复杂度为O（n）。
去重：
templateint Vector ::deduplicate() { //删除无序向量中重复元素（高效版） int oldSize = _size; //记录原规模 Rank i = 1; //从_elem[1]开始 while ( i < _size ) //自前向后逐一考查各元素_elem[i] ( find ( _elem[i], 0, i ) < 0 ) ? //在其前缀中寻找与之雷同者（至多一个） i++ : remove ( i ); //若无雷同则继续考查其后继，否则删除雷同者 return oldSize - _size; //向量规模变化量，即被删除元素总数}
去重的思路可描述为从前往后遍历向量，遍历到秩为i的元素时，向前搜索有没有相同的元素，有则删除秩为i的元素，没有则i++，继续考察下一个元素。这里较好的情况下没有找到重复元素，i一直右移即可，最坏情况下每次循环，首先向前找有没有重复的，找到重复的删除秩为i的元素，又将后面的元素一个个前移，消耗的总的复杂度是O（n），遍历完成总的时间复杂度为O（n^2）.
正确性证明：
不变性：v[i]的前缀v[0,i]中，各元素彼此互异。
单调性：当前元素前缀长度单调非降，且迟早增至size；当前元素后缀的长度单调下降，且迟早减至0.
遍历：
方法一：函数指针
具体的操作定义在函数里，通过函数指针来遍历vector。
templatevoid Vector ::traverse ( void ( *visit ) ( T& ) ) //借助函数指针机制{ for ( int i = 0; i < _size; i++ ) visit ( _elem[i] ); } //遍历向量
方法二：函数对象
templatetemplate //元素类型、操作器void Vector ::traverse ( VST& visit ) //借助函数对象机制{ for ( int i = 0; i < _size; i++ ) visit ( _elem[i] ); } //遍历向量
比如：
templatestruct Increase{ virtual void operator() (T &e){e++;}};template void increase(vector &v){ v.traverse(Increase ());}
有序向量
唯一化
用相邻逆序对的数目来度量向量的逆序程度。
统计相邻逆序对数目算法：
templateint Vector ::disordered() const { //返回向量中逆序相邻元素对的总数 int n = 0; //计数器 for ( int i = 1; i < _size; i++ ) //逐一检查_size - 1对相邻元素 if ( _elem[i - 1] > _elem[i] ) n++; //逆序则计数 return n; //向量有序当且仅当n = 0}
有序向量的去重
低效算法：
templateint Vector ::uniquify() { //有序向量重复元素剔除算法（低效版） int oldSize = _size; int i = 1; //当前比对元素的秩，起始于首元素 while ( i < _size ) //从前向后，逐一比对各对相邻元素 _elem[i - 1] == _elem[i] ? remove ( i ) : i++; //若雷同，则删除后者；否则，转至后一元素 return oldSize - _size; //向量规模变化量，即被删除元素总数}
该算法在遍历向量的时候，比较相邻元素是否相等，相等则删除后者，否则继续遍历下一个位置。最坏情况下，比如1 1 1 1 …，指向该算法，从第二个1开始，需要不断的执行删除操作，重复n-1次，每次的复杂度是O（n），总的时间复杂度为平方级别。
该算法低效的根源在于同一元素可作为被删除元素的后继多次被前移。
高效算法：
templateint Vector ::uniquify() { //有序向量重复元素剔除算法（高效版） Rank i = 0, j = 0; //各对互异“相邻”元素的秩 while ( ++j < _size ) //逐一扫描，直至末元素 if ( _elem[i] != _elem[j] ) //跳过雷同者 _elem[++i] = _elem[j]; //发现不同元素时，向前移至紧邻于前者右侧 _size = ++i; shrink(); //直接截除尾部多余元素 return j - i; //向量规模变化量，即被删除元素总数}
不再显式的执行删除操作，用i记录新向量的末尾位置，遇见不重复的元素则覆盖掉到i后面的元素，同时i++，遇见重复的不做处理，最后将新向量的size置为i即可。
例如 1 1 1 2 2 2 3 3 3 3，执行一遍遍历得到1 2 3 2 2 2 3 3 3 3，size被置为3.
总的时间复杂度为O（n）。
PS：algorithm头文件里面的unique函数应该就是基于该算法实现的，所以在离散化算法中，对向量进行排序后，需要先unique再erase完最后才能进行哈希映射。
有序向量二分查找
语义约定：
一般情况下，含有重复元素的有序向量中，我们查找值为e的元素，如果含有多个元素值为e，则应该返回哪个e的秩呢？这个约定为返回不大于e的最后一个元素的秩，如果没有找到e，则返回的秩的后一个位置就可以作为e的插入位置了。
考虑到算法的鲁棒性，如果所有元素都大于e，则应该返回最左边元素秩-1；如果所有的元素都大于e，则应该返回最后一个元素的秩。
首先实现不完全按照上面语义约定二分的算法，仅仅找到了就返回，找不到就返回-1.
三分的思想：
查找[lo,hi]（左闭右开）范围内的某元素，取中点mid，待查找元素e小于中间元素，则hi = mid，e大于中间元素，则lo = mid + 1，e等于中间元素，则返回mid。
// 二分查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
templatestatic 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 ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找 else return mi; //在mi处命中 } //成功查找可以提前终止 return -1; //查找失败} //有多个命中元素时，不能保证返回秩最大者；查找失败时，简单地返回-1，而不能指示失败的位置
注：这里在比较时都采用小于号，是因为小于号的左右顺序与元素实际顺序一致，便于理解。
显然二分查找的时间复杂度为O（logn）。
查找长度：关键码的比较次数。
成功、失败时的平均查找长度均大致为O（1.5logn）。
一般用比较树来形象的判断比较次数。
可见，符合向左查找条件时，只需要进行一次比较，而符合向右查找条件或者命中时，在该结点需要经过两次比较。所有的非叶结点均代表着一次成功的查找，所有虚线连接的叶结点均代表着一次失败的查找。由此可见，当待查找元素较小时，查找次数较少。也就是比较树左边结点的比较次数要小于右边结点的比较次数。
有序向量Fibonacci查找
二分查找比较树左右深度相同，比较次数却不同，改变轴点的位置，通过深度的不均衡，对转向成本的不均衡进行补偿。
设n = fib（k） - 1，则可以取轴点mi = fib（k-1）-1，则左边向量的长度为fib（k-1）-1，右边向量的长度为fib（k-2）-1.
templatestatic Rank fibSearch ( T* A, T const& e, Rank lo, Rank hi ) { Fib fib ( hi - lo ); //用O(log_phi(n = hi - lo)时间创建Fib数列 while ( lo < hi ) { //每步迭代可能要做两次比较判断，有三个分支 while ( hi - lo < fib.get() ) fib.prev(); //通过向前顺序查找（分摊O(1)）——至多迭代几次？ Rank mi = lo + fib.get() - 1; //确定形如Fib(k) - 1的轴点 if ( e < A[mi] ) hi = mi; //深入前半段[lo, mi)继续查找 else if ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找 else return mi; //在mi处命中 } //成功查找可以提前终止 return -1; //查找失败} //有多个命中元素时，不能保证返回秩最大者；失败时，简单地返回-1，而不能指示失败的位置
可见，斐波那契查找与二分查找的区别仅在于轴点的选取上，Fbonacci查找的ASL（在常系数意义上）要优于二分查找。注意：二者的渐进时间复杂度仍然是相同的，只不过有常系数上的区别。
注：fib查找如果选取右侧的fib轴点会导致右边的深度和比较次数都偏高，故不可选fib(k-2)-1作为轴点。
有序向量二分查找（版本二）
解决之前二分查找中左右转向代价不均衡的问题，也可以直接解决。
如果每次迭代仅做一次关键码比较，变三分为二分，转向的代价便是均衡的了。
由于关键码比较条件的修改，使得只有当区间长度为1时，算法才会终止，而原来的二分查找只要找到待查找元素，算法会立刻终止，所以下面的算法在各种情况下更加趋于稳定。
templatestatic 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; //经比较后确定深入[lo, mi)或[mi, hi) } //出口时hi = lo + 1，查找区间仅含一个元素A[lo] return ( e == A[lo] ) ? lo : -1 ; //查找成功时返回对应的秩；否则统一返回-1} //有多个命中元素时，不能保证返回秩最大者；查找失败时，简单地返回-1，而不能指示失败的位置
二分查找（版本三）
templatestatic 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为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩} //有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置
版本三只是返回了之前语义约定的不大于待查找元素的秩，个人认为有多种实现方式，区间的开闭以及关键码比较是否带等号都具有灵活性。
插值查找：
如果已知有序向量中各元素随机分布的规律，比如均匀且独立的随机分布，lo到hi区间内的元素应该大致按照线性趋势增长。
性能：
最坏情况下自然是O（n）。
平均情况下每经一次比较，待查找区间的宽度由n降为根号n，最后查找的范围应该有n^(1/2^k) < 2,得到1/2^k * logn < 1,k = O（loglogn）。也就是说插值查找的时间复杂度为O（loglogn）。
由于每次查找查找宽度由n变为根号n，n的二进制长度为logn，则根号n的二进制长度为0.5logn，也就是说每次比较，待查找区间长度的有效字长减半。
由于一个很大的数取对数后规模会骤减，而再次取对数效果并不明显，相反，如果出现了插值查找的比较坏的情况还会造成查找次数的增加。所以，一般大规模有序向量的查找首先使用插值查找将规模降下来，然后再进行二分查找。对于规模很小的有序向量，顺序查找足以满足要求。
起泡排序：
templatevoid Vector ::bubbleSort(Rank lo,Rank hi){while(!bubble(lo,hi--));}//逐趟做扫描交换，直至全序。template bool Vector ::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;}
上面的算法能在扫描到没有相邻逆序对的情况下直接结束，若乱序的元素不超过根号n，则扫描次数不超过根号n，一共需要O（n^(3/2)）时间。
也就是说2 1 3 4 5，一次扫描后得到1 2 3 4 5，就可以结束算法了。不足的是比如3 2 1 4 5 6，一趟扫描交换后得到2 1 3 4 5 6，然后第二趟扫描依旧要遍历所有的元素进行比较，可以发现，第一趟扫描结束最后一次发生交换的是3 和 1，也就是3到达它所在的位置后，后面的元素没有发生交换，说明3以后的元素序列不存在逆序对，故以后的扫描交换不需要再去比较3后面的元素了。
改进算法：
templatevoid Vector ::bubbleSort(Rank lo,Rank hi){while(lo < (hi = bubble(lo,hi)));}template bool Vector ::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;}
改进后的算法记录下了每次扫描最后一次发生逆序对交换的位置last，下次只要扫描last之前的元素即可。这样一来，最多根号n次扫描，大部分扫描的位置也都在前根号n个元素内，时间复杂度是O（n）。
总的来说，起泡排序的时间复杂度最好是O（n），最坏是O（n^2）。
而且在算法中，只有前面元素严格大于后面元素才会发生逆序对的交换，所以算法是稳定的。
向量归并排序
上面代码涉及到的merge函数实现如下：
template//有序向量的归并void Vector ::merge ( Rank lo, Rank mi, Rank hi ) { //各自有序的子向量[lo, mi)和[mi, hi) T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi) int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi) for ( Rank i = 0; i < lb; B[i] = A[i++] ); //复制前子向量 int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi) for ( Rank i = 0, j = 0, k = 0; ( j < lb ) || ( k < lc ); ) { //B[j]和C[k]中的小者续至A末尾 if ( ( j < lb ) && ( ! ( k < lc ) || ( B[j] <= C[k] ) ) ) A[i++] = B[j++]; if ( ( k < lc ) && ( ! ( j < lb ) || ( C[k] < B[j] ) ) ) A[i++] = C[k++]; } delete [] B; //释放临时空间B} //归并后得到完整的有序向量[lo, hi)
具体思路为：用数组A存放待合并的序列lo到hi中元素，mi左边元素和右边元素分别用B和C存，用j和k分别表示B、C数组合并的进度，只要未越界，当j和k都未越界时，将B[j]和C[k]中较小者赋给A，一旦一方越界另一方未越界，直接将未越界的全部赋给A。
精简实现：
for ( Rank i = 0, j = 0, k = 0; j < lb; ) { //将B[j]和C[k]中的小者续至A末尾 if ( ( k < lc ) && ( C[k] < B[j] ) ) A[i++] = C[k++]; if ( ( lc <= k ) || ( B[j] <= C[k] ) ) A[i++] = B[j++];}/*DSA*/ //交换循环体内两句的次序，删除冗余逻辑 相对于之间版本的变化是，一旦B数组率先全部被合并完，则终止合并，因为C数组还未进行合并的部分本来就是A数组的右侧部分，无须再重复地进行合并。
归并排序的时间复杂度无论是最好情况下还是最好情况下都是O（nlogn）.
转载地址：https://blog.csdn.net/qq_30277239/article/details/102916876 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
