（以下均由 c / c++ 实现，由于不是很会，如果代码有问题，欢迎指出）
ADT vs. Data Structure
● ADT
○ 数据模型 + 定义在该模型上的一组操作
● Data Structure
○ 基于某种特定语言，实现 ADT 的一整套算法
Vector [ c++ 实现 ]
● 内部开辟一个数据区
● 构造：_elem = new T[_capacity = c ]
● 析构：delete [] _elem
● void Vector<T>::copyFrom
Vector 内部空间管理
静态空间管理
● 内部数组：_elem[]
● 总容量：_capacity
● 当前的实际规模：_size
● 问题：上溢 / 下溢（装填因子）
动态空间管理
● 在即将发生上溢时，适当地扩大内部数组的容量
● new 一个新的容量更大的数组，将数组内数据复制过去，并 delete 原来数组
// 扩容算法实现
void Vector<T>::expand(){ // 向量空间不足时扩容
if( _size < _capacity ){
return; // 尚未满员时，不必扩容
}
_capacity = max(_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; // 释放原空间
}
无序向量
元素访问
● 像数组一样访问
● 重载 下标操作符 “[]”
○ typedef int Rank;
○ template <typename T>
○ T & Vector<T>::operator[](Rank r) const { return _elem[r]; }
有序向量
唯一化
template <typename T> int Vector<T>::uniquely(){
Rank i = 0, j =0; // 各对互异“相邻”元素的秩
while( ++j < _size ){ // 逐一扫描，直至末元素
// 跳过雷同者，发现不同元素时，向前移至紧邻于前者右侧
if( _elem[i] != _elem[j] ){
_elem[++i] = _elem[j];
}
}
_size = ++i;
shrink(); // 直接截除尾部多余元素
return j - i; //向量规模变化量，即被删除元素总数
}
二分查找
search(char c, int low, int high);
● 返回 [low, high) 内不大于 c 的最后一个元素的秩
● 如果 V[low] > c，返回 (low - 1)
● 如果 V[high-1] < c，返回 (high - 1)
image.png
● T(n) = T(n / 2) + O(1) = O(logn)
● 成功和失败的平均查找长度大致为 1.5*logn
image.png
使得向左和向右的成本相等，三个分支 改为 两个分支
相对于原来的算法，最好的情况由 O(1) 变为 O(logn)，但最坏的情况有所改善，总体性能上趋于稳定
Fibonacci 查找
由于之前算法的向左成本为1，向右成本为2，所以使得查找尽量向左查找深度更深
image.png
插值查找
均匀独立的随机分布
image.png
mi ≈ lo + (hi - lo) * (e - A[lo]) / (A[hi] - A[lo])
性能分析
平均情况：每经过一次 插值查找 算法，就能将查找范围从 n 缩至 √n
复杂度 = O(log logn)（不太确定）
起泡排序（冒泡排序）
原操作：每次扫描交换所有逆序对
改进：每一次扫描的过程中交换所有逆序对，如果此次扫描中没有此操作，就停止扫描退出
再改进：记录每一次扫描最后一个交换的元素的位置（只需交换一次）
归并排序
image.png
原理
image.png
实现
image.png
性能分析
T(n) = 2T(n/2) + O(n) = 2^logn T(1) + O(nlogn) = nT(1) + O(nlogn) = O(n) + O(nlogn) = O(nlogn)
// T(n) 展开到 T(1) 会产生 logn 个 O(n)，虽然系数不同。
