向量

发表于 分类于

在导论中，我们了解到数据结构是若干数据项的结构化集合，其结构性表现为数据项之间的某种逻辑次序。根据这种逻辑次序的复杂程度可大致将数据结构分为线性、半线性、非线性结构三大类。在线性结构中，各数据项按照一个线性次序组织为一个整体。在向量中，所有数据项的物理存放位置与其逻辑次序完全吻合。

在C/C++语言中，数组支持对一组相关元素的存储组织和访问操作。若集合S由$n$个元素组成，则可将它们存放于起始于地址A、物理地址连续的一段存储空间，并统称为数组。数组A[]中每一元素都唯一对应于某一下标编号。反之，每个元素均由非负编号唯一指代，并可直接访问。

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

静态空间管理

内部数组所占物理空间的容量，若在向量的生命周期内不允许调整，则称为静态空间管理策略。

上溢 数组不足以存放所有元素，尽管系统此时仍有足够的空间

下溢 元素寥寥无几，即装填因子(向量实际规模和内部数组容量的比值)远远小于50%.

动态空间管理

一般的应用环境难以准确预测空间的需求量，使向量可随实际需求动态调整容量，在即将发生上溢时适当扩大向量的容量。

可扩充向量

倍增策略 每次新数组的容量总是取作原数组的两倍

1
2
3
4
5
6
7
8
template <typename T> void Vector<T>::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; //释放原空间
}

最坏情况：在初始容量为0的空向量中，连续插入$n=mI>>2$个元素

于是在第$1，2,4,8…$次插入时都需扩容，

即便不计申请空间操作，各次扩容过程中复制原向量的时间成本依次为

$1,2,4,8,…,2^m=n$

总体耗时$O(n)$,每次扩容的分摊成本为O(1)

递增策略

1
T* oldElem = _elem;  _elem = new T[_capacity+increment];

最坏情况：在初始容量为0的空向量中，连续插入$n=mI>>2$个元素

于是在第$1，I+1,2I+1,3I+1…$次插入时都需扩容，

即便不计申请空间操作，各次扩容过程中复制原向量的时间成本依次为

$0,I,2I,3I,..(m-1)I$

每次扩容的分摊成本为$O(n)$

分摊分析

平均分析和分摊分析

平均复杂度

在假定各种输入实例的出现符合某种概率分布后，对对应成本加权平均。

各种可能的操作，作为独立事件分别考查，割裂了操作之间的相关性和连贯性

往往不能准确地评价数据结构和算法的平均性能

分摊复杂度

对数据结构连续地实施足够多次操作，所需总体成本分摊至单次操作

从实际可行的角度，对一系列操作做整体的考量

更加忠实得刻画了可能出现的操作序列

更为精准地评判数据结构和算法地真实性能

条件不规整时，可添加约束，比如$n=2^k$

无序向量

置乱算法

在软件模拟、仿真测试等应用中，随机向量的生成都是一项至关重要的操作。理论上说，调用permute可以枚举出同一向量所有可能的排列，而且能够保证生成各种序列的概率相等。但是基于种子的伪随机数发生器无法保证所生成随机数之间的独立性，所以无法等可能地生成所有排列。

1
2
3
4
template <typename T> void permute ( Vector<T>& V ) { //随机置乱向量，使各元素等概率出现于各位置
   for ( int i = V.size(); i > 0; i-- ) //自后向前
      swap ( V[i - 1], V[rand() % i] ); //V[i - 1]与V[0, i)中某一随机元素交换
}

查找

1
2
3
4
5
template <typename T> //无序向量的顺序查找：返回最后一个元素e的位置；失败时，返回lo - 1
Rank Vector<T>::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即命中元素的秩
}

约定在命中多个元素时可返回秩最大者

输入敏感算法，,最好$O(1)$,最差$O(n)$

插入

1
2
3
4
5
6
7
template <typename T> //将e作为秩为r元素插入
Rank Vector<T>::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; //返回秩
}

为了避免元素被覆盖，自后向前对元素操作。时间复杂度主要取决于后继元素的后移，故总体为$O(size-r+1)$，r取最大值size时只需$O(1)$时间，r取最小值时需要$O(size)$时间，平均时间正比于向量规模。

删除

区间删除

1
2
3
4
5
6
7
template <typename T> int Vector<T>::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; //返回被删除元素的数目
}

单元素删除可视为区间删除操作的特例

此处自前向后的顺序不可颠倒，否则在后继元素多于待删除元素后部分单元会相互覆盖。每次操作正比于删除区间的后缀长度$=n-hi=O(n)$，与被删除区间本身的长度无关，循环次数等于区间宽度$=hi-lo=O(n)$,总体复杂度为$O(n^2)$

单元素删除

时间复杂度$O(n-r)$，被删除元素在向量中的位置越靠后所需的时间越短，最好为$O(1)$,最坏为$O(n)$

去重

应用实例：以网络搜索引擎为例，多个计算节点各自获得的局部搜索结果需首先剔除其中重复的部分，方可汇总成一份完整的报告。

错误版

1
2
3
4
5
6
7
8
template <typename T> int Vector<T>::deduplicate() { //删除无序向量中重复元素（错误版）
   int oldSize = _size; //记录原规模
   for ( Rank i = 1; i < _size; i++ ) { //逐一考查_elem[i]
      Rank j = find ( _elem[i], 0, i ); //在_elem[i]的前驱中寻找与之雷同者（至多一个）
      if ( 0 <= j ) remove ( j ); //若存在，则删除之（但在此种情况，下一迭代不必做i++）
   }
   return oldSize - _size; //向量规模变化量，即被删除元素总数
}

在前驱存在相同元素时，删除该元素时该元素所有后继均会向前移动一个单位，所以此时$i$不必后移，后移将会跳过元素，此算法错误。

繁琐版

1
2
3
4
5
6
7
8
9
10
template <typename T> int Vector<T>::deduplicate() { //删除无序向量中重复元素（繁琐版）
   int oldSize = _size; //记录原规模
   int i = -1; //从最前端开始
   while ( ++i < _size - 1 ) { //从前向后，逐一
      int j = i + 1; //assert: _elem[0, i]中不含重复元素
      while ( j < _size )
         if ( _elem[i] == _elem[j] ) remove ( j ); //若雷同，则删除后者
         else j++; //并继续扫描
   }
   return oldSize - _size; //向量规模变化量，即被删除元素总数

此算法在处理时不同于前一方法，在雷同元素中删除后者，避免了跳过元素的问题，元素的移动操作与之前的算法相比也有所减少,同时查找操作会有所增加。

1
2
3
4
5
6
7
template <typename T> int Vector<T>::deduplicate() { 
   int oldSize = _size; //记录原规模
   int i=1;
   while(i<size)
	   find(_elem[i],0,i)<0 ? i++ :remove(i);
   return oldSize - _size; //向量规模变化量，即被删除元素总数
}

算法分析

正确性 凡被剔除者均为重复元素(不多)，故只需证明，算法不致遗漏重复元素(不少)。

不变性 在当前元素V[i]的前缀V[0,i)中，各元素彼此互异

单调性 随着反复的while迭代，

  1. 当前元素的前缀长度单调非降，且迟早增至size
  2. 当前元素后缀的长度单调下降，且迟早降至0

故算法必然终止，且至多迭代$O(n)$轮

复杂度 每轮迭代中find()和remove()累计耗费线性时间，总体$O(n^2)$

即便在最好情况下，仍然需要运行$\Omega(n^2)$时间，每次迭代都需要做一次查找操作和一次可能的删除操作，对于_elem[k],若需要做删除操作，为此需花费$O(n-k)$，反之，若不需要做删除操作，则此前的查找操作以失败告终，其间已花费了$O(k)$时间，无论如何，每次迭代需要$\Omega(min(n-k,k))$时间，累计为$\Omega (n^2)$

  • 仿照uniquify高效版思路，元素移动的次数可降低至$O(n)$，但是比较次数仍然是$O(n^2)$。在发现重复元素后不必立即剔除，借助位图结构先对需删除的重复元素标记，然后再统一删除，稳定性保持，但是查找长度更长，从而导致更多比对操作。时间消耗主要来源于静态的比较操作，所以实际运行时间仍将大幅提高。

改进方法

可先对无序向量进行排序，后再调用有序向量的唯一化方法，总时间为$O(nlogn)+O(n)=O(nlogn)$

有序向量

有序性

有序/无序序列中，任意/总有一对相邻元素顺序/逆序。

因此，相邻逆序对的数目，在一定程度上可用来度量向量的逆序程度。

1
2
3
4
5
6
7
template <typename T>  int Vector<T>::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
}

唯一化

低效算法

1
2
3
4
5
6
template <typename T> int Vector<T>::uniquify() { 
   int oldsize=_size,int i=1;
   while(i<_size)
     _elem[i-1]==elem[i]?remove[i]:i++;
   return oldsize-_size;
}

运行时间主要取决于while循环次数，共计数$n-1$次

最坏情况下，每次都需要调用remove(),各自耗时$O(n-1)$~$O(1)$，累计$O(n^2)$

低效的根源在于同一元素可作为被删除元素的后继多次被前移。

高效算法
有序向量每一组重复元素必然相互紧邻构成一个重复区间，所谓去重就是为每一重复区间保留单个元素，以重复区间为单位，成批删除雷同元素。

1
2
3
4
5
6
7
8
template <typename T> int Vector<T>::uniquify() { //有序向量重复元素剔除算法（高效版）
   Rank i = 0, j = 0; //各对互异“相邻”元素的秩
   while ( ++j < _size ) //逐一扫描，直至末元素
      if ( _elem[i] != _elem[j] ) //跳过雷同者
         _elem[++i] = _elem[j]; //发现不同元素时，向前移至紧邻于前者右侧
   _size = ++i; shrink(); //直接截除尾部多余元素
   return j - i; //向量规模变化量，即被删除元素总数
}

共计$n-1$次迭代，累计$O(n)$时间。

二分查找

版本a

1
2
3
4
5
6
7
8
9
template <typename T> static 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，而不能指示失败的位置

尽管二分查找将之前的向量分为了两部分，却不是二分递归，而是线性递归。每一实例有两个可能的递归方向，却只能从中选择其一，故每个层次上的递归实例构成一个线性次序关系。

递推方程分析

$T(n)=T(n/2)+O(1)=O(logn)$,大大优于顺序查找

递归跟踪分析

轴点总取作中点，递归深度$O(logn)$,各递归实例均耗时$O(1)$

查找长度

为了更为精细地评估查找算法地性能，考查关键码的比较次数。

分别针对成功查找和失败查找，从最好、最坏、平均情况等角度评估。

对于长度为$n$的有序向量，共有$n$种可能的成功查找，分别对应于某一元素。实际上，每一种成功的查找长度仅仅取决于$n$和目标元素所对应的秩，而与元素的具体数值无关。

将平均的成功查找长度和失败查找长度分别记作S和S’,则(S+1)n=F(n+1)

成功查找长度和失败查找长度均为$O(1.5logn)$

在每一步迭代过程中为了确定左右分支方向，需要做一次或两次比较，从而造成不同情况对应查找长度的不均衡。

转向左右分支的关键码比较次数不等，而递归深度却相同。

为了改善均衡性，有两种解决思路：

  • 通过递归深度的不均衡，对转向成本进行补偿，缩短平均查找长度
  • 统一沿两个方向深入需要执行的比较次数

版本b

每次迭代时仅做1次关键码比较，如此，所有的分支只有2个方向而不是3个方向

1
2
3
4
5
6
7
template <typename T> static 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)
   } //有效区间的宽度缩减至1时算法才会终止
   return ( e == A[lo] ) ? lo : -1 ; //查找成功时返回对应的秩；否则统一返回-1
} //有多个命中元素时，不能保证返回秩最大者；查找失败时，简单地返回-1，而不能指示失败的位置

只有当元素数目$hi-lo=1$时才判断元素是否命中。

knuth指出将三分支改为两分支的改进效果需要到n非常大(2^66)后方能体现，针对当前规模来说，这一优化得不偿失。

版本c

1
2
3
4
5
6
7
template <typename T> static 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的元素的最大秩
} //有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置

待查找区间宽度缩减为0时算法结束，返回不大于e的最后一个元素，此前的版本均未实现此约定。

不变性

在算法执行的任意过程中，A[lo-1]/A[hi]​总是当前不大于e的最大者/大于e的最小者

当算法终止时，A[lo-1]/A[hi]​即是全局的大于e的最大者/大于e的最小者

斐波那契查找

二分查找版本A转向左右分之前的关键码比较次数不相等，而递归长度却相同，通过递归深度的不平衡对转向成本的不平衡进行补偿，平均查找长度可进一步缩短。

1
2
3
4
5
6
7
8
9
10
template <typename T> static 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的轴点
      ( e < A[mi] ) ? hi = mi : lo = mi + 1; //比较后确定深入前半段[lo, mi)或后半段(mi, hi)
   } //成功查找不能提前终止
   return --lo; //循环结束时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
} //有多个命中元素时，总能保证返回最秩最大者；查找失败时，能够返回失败的位置

成功平均查找长度为$O(log_{\phi}n)=O(log_{\phi}nlog_{2} \phi)=O(1.44log_2{n})$\

失败平均查找长度不超过$\lambda log_2{n+1}=O(\lambda log_2{n})$

其中$\lambda=1+1/\phi^2=3-\phi=1.382$

通用策略

索引查找

$m$级索引，每一级索引内部采用顺序查找，可将查找的时间复杂度降低至$n^{1/m}$

插值查找

假设：已知有序向量中各元素随机分布的规律，比如：均匀且独立的随机分布，

于是[lo,hi)内各元素应大致按照线性趋势增长

$\displaystyle \frac{mi-hi}{hi-lo} \approx \frac{e-A[lo]}{A[hi]-A[lo]}$

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

$\displaystyle mi \approx lo+(hi-lo)\frac{e-A[lo]}{A[hi]-A[lo]} $

以英文字典为例，binary大致位于$2/26$处

search大致位于$19/26$处

性能分析

最坏:$O(hi-lo)=O(n)$

平均:每经过一次比较，待查找区间宽度由$n$缩至$\sqrt{n}$

$n,\sqrt{n},\sqrt{\sqrt{n}},…,2$

$n,n^{1/2},n^{1/2^2},n^{1/2^{k}},…,2$

经过$k$次比较后，$n^{1/2^k}<2$,$k=O(loglogn)$

每经过一次比较，待查找区间宽度地数值开放，有效字长减半

插值查找为在字长意义上地折半查找

二分查找为在字长意义上的顺序查找

从$O(logn)$到$O(loglogn)$,是否值得？

通常优势不明显，除非查找区间宽度极大，或者比较操作成本极高

比如,$n=2^(2^5)=2^{32}=4G$时，$log2{n}=32,log_2(log_2(n))=5$

易受小扰动的干扰和蒙骗

须引入乘法和除法运算

可先通过插值查找将查找范围缩小至一定的尺度，然后再进行二分查找

每经过一次插值和查找，待搜索区间的宽度大致以平方根的速度递减

最坏情况下仍然为$O(n)$，即极端不平衡的情况，{1,2,2000,2001,999999,9999999}

假设数据在某个范围内均匀分布，插值查找每经过一次比较，待搜索区间以平方根速度递减。时间复杂度为$O(loglogN)$。需要注意，$O(loglogN)$的复杂度是平均期望复杂度，而不是最坏情况复杂度。

起泡排序

1
2
3
4
5
6
7
8
9
10
11
void Vector<T>::bubbleSort ( Rank lo, Rank hi ) //assert: 0 <= lo < hi <= size
{ 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; //返回有序标志
}

在对$n$个元素做起泡排序的过程中，可能会发生：

  • 所有元素均无需移动
  • 某元素会一度(朝着远离其最终位置的方向)逆向移动
  • 某元素的初始位置与其最终位置相邻，却需要参与$n-1$次交换
  • 所有元素均参加$n-1$次交换

稳定算法的特征是，重复元素之间的相对次序在排序前后保持一致。反之，不具有这一特征的排序算法都是不稳定算法。以上排序算法是稳定的，在起泡排序算法中，元素相对位置调整的唯一可能是某元素_elem[i-1]严格大于其后继_elem[i]。也就是说，在这种亦步亦趋的交换算法中，重复元素可能靠拢，但绝对不会相互跨越。由此可知，起泡排序算法为稳定算法。

乱序在$A[0,\sqrt{n}]$时，仍然需要调用bubble(),共做$\Omega(n)$次交换操作和$\Omega(n^{3/2})$次比较操作，外循环$\sqrt{n}$次，内循环$n$次

优化 返回最右侧逆序对的位置

1
2
3
4
5
6
7
8
9
10
11
void Vector<T>::bubbleSort ( Rank lo, Rank hi ) //assert: 0 <= lo < hi <= size
{ while ( lo < ( hi = bubble ( lo, hi ) ) ); } //逐趟做扫描交换，直至全序
template <typename T> Rank Vector<T>::bubble ( Rank lo, Rank hi ) { //一趟扫描交换
   Rank last = lo; //最右侧的逆序对初始化为[lo - 1, lo]
   while ( ++lo < hi ) //自左向右，逐一检查各对相邻元素
      if ( _elem[lo - 1] > _elem[lo] ) { //若逆序，则
         last = lo; //更新最右侧逆序对位置记录，并
         swap ( _elem[lo - 1], _elem[lo] ); //通过交换使局部有序
      }
   return last; //返回最右侧的逆序对位置
}

同样以乱序只存在$A[0,\sqrt{n}]$时，仅需一趟扫描交换$O( n )$即可确定逆序数存在的空间，累计耗时：

$O(n+(\sqrt n)^2)$=$O(n)$

归并排序

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>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
   if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
   int mi = ( lo + hi ) / 2; //以中点为界
   mergeSort ( lo, mi ); mergeSort ( mi, hi ); //分别排序
   merge ( lo, mi, hi ); //归并
}
template <typename T> //有序向量的归并
void Vector<T>::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)

综合评价

优点

  • 实现最坏情况下最优$O(nlogn)$性能的第一个排序算法
  • 不许随机读写，完全顺序访问，尤其适用于列表之类的序列和磁盘之类的设备
  • 只要实现得当，可保证稳定，在出现雷同元素时，左侧子向量优先
  • 可扩展性极佳，十分适宜于外部排序(海量网页搜索结果的合并)
  • 易于并行化

缺点

  • 非就地，需要对等规模的辅助空间
  • 即便输入完全(接近)有序，仍需$O(nlogn)$时间

优化

在最好情况下仍然需要$O(nlogn)$时间，在业已有序的情况下不必再合并，每个递归实例为常数时间，复杂度优化至$O(n)$。以mi为界划分为两个子序列A[lo,mi),A[mi,hi)，若后一个子序列的最小值大于等于前一个子序列的最大值，则已有序，无需再合并。

1
2
3
4
5
6
7
template <typename T> //向量归并排序
void Vector<T>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
   if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
   int mi = ( lo + hi ) / 2; //以中点为界
   mergeSort ( lo, mi ); mergeSort ( mi, hi ); //分别排序
   if(_elem[mi-1]>_elem[mi])merge ( lo, mi, hi ); //归并
}

排序与下界

从数据处理的角度来看，有序性在很多场合都可以极大地提高计算效率。在解决许多应用问题时普遍采用的一种策略就是首先将向量转换为有序向量，再调用有序向量支持的各种高效算法，这一过程就是向量的排序。

以下给出排序的准确定义：

任意给定N个元素${R1,R2,…,Rn}$,对应关键码${K1,…,Kn}$,需按某种次序排列。亦即是找出$<1,2,3,..,n>$的一个排列，使得$K_{i1}\leq K_{i2}\leq K_{i3}\leq…\leq K_{in}$

例如，$3,1,4,1,5,9,2,6$ 经排序后的序列为$1,1,2,3,4,5,6,9$

在实际应用中，25%到50%的计算都可以归于排序。

排序算法是个庞大的家族，其中根据处理数据的规模和存储的特点不同，分为内部排序算法和外部排序算法，内部排序是数据记录在内存中进行排序，而外部排序因为排序的数据很大，一次不能容纳全部的排序记录，在排序的过程中需要访问外存。

根据输入方式的不同，可分为在线算法和离线算法。前一情况下，待排序算法通常以批处理的形式整理给出，在网络计算等环境中，待排序的算法通常需要实时生成，在排序算法启动后数据才陆续到达。

再如，针对所依赖的体系结构的不同，排序算法又可分为串行和并行两类排序算法。另外，根据算法是否采用随机策略，还有确定式和随机式之分。

下界

在着手优化算法时，我们首先需要解决以下几个问题

  • 起泡排序的复杂度为$O(n^2)$,归并排序算法的复杂度为$O(nlogn)$,这一效率是否已经足够高？
  • 能否以更快的速度完成排序

考虑以下问题：三只苹果外观一致，其中两只重量相同另一只不同，利用一架天平如何从中找出重量不同的那只？

以上问题所需的最少比较次数为多少次？

尽管很多算法都可以优化，但是对任一特定应用问题随着算法的不断改进，其效率的提高必然存在某一极限。这一极限不仅必然存在，其具体的数值应取决于应用问题本身以及所采用的计算模型。

一般地，任一问题在最快情况下的最低计算成本，即为该问题的复杂度下界，一旦某一算法的性能达到这一下界，即意味着它已经是最坏情况下最优的。

比较树

若用结点表示算法中的不同状态，用有方向的边表示不同状态之间的转换相互转换。

一般地，树根结点对应于算法入口处的起始状态，内部结点对应于过程中的某步计算，通常属于基本操作，叶结点则对应于经一系列计算后某次运行的终止状态。

算法所有可能的执行过程都可涵盖于比较树中。具体地，该树具有以下性质

  • 每一内部节点对应于一次比对操作
  • 内部节点的左右分支分别对应于在两种比对操作下的执行方向
  • 叶节点(根到叶节点的路径)对应于算法某次执行的完整过程及输出
  • 反过来，算法的每一次运行都对应于从根到某一叶节点的路径

按上述规则与算法对应的树称为比较树。无论什么算法，只要其中的分支都完全取决于不同变量或常量的比对或比较结果，则该算法所有可能的执行过程都对应于从根到某一叶节点的路径。反之，可如此描述的算法都称为基于比较式算法，简称CBA式算法。

估计下界

考查任一CBA式算法A,设CT(A)为与之对应的一棵比较树。

根据比较树的性质，算法A每次运行的时间都取决于其对应叶节点到根节点的距离，而算法A在最坏情况下的运行时间将取决于比较树中所有叶节点的最大深度，即该树的高度，记作h(CT(A))。就渐进意义而言，算法A的时间复杂度应不低于h(CT(A))。

以苹果鉴别为例，可能的输出结果有N=3种，故解决该问题的任一CBA式算法所对应比较树的高度为：

$h \geq \lceil log_23 \rceil=2$

因此，只要是采用CBA式算法，则无论如何优化，在最坏情况下都至少需要2次称量。

再以CBA式排序算法为例,$n$个元素而言，可能的输出有$n!$种，元素之间不仅可以判等还可以比较大小，因此每一节点都对应有三个分支(分别对应大于、等于、小于的情况)。任一CBA式排序算法对应比较树的高度为：

$h \geq \lceil log_3{n!}\rceil=\Omega(nlogn)$

可见，最坏情况下CBA式排序算法至少需要$\Omega(nlogn)$时间，其中$n$为待排序元素的数目。

这一复杂度下界是针对基于比较树的模型而言的，很多不属于此类型的算法在最坏情况下的复杂度可能低于这一下界。

归约

除了比较树，归约同样也是证明下界的有力工具。

一般地，考查难度待界定的问题B，若另一问题A满足以下性质：

  • 问题A的任一输入，在线性时间内可以转换为问题B的输入
  • 问题B的任一输出，在线性时间内可以转换为问题A的输出

则称问题A在线性时间内归约为问题B，若问题A的难度已界定为严格地高于$\Omega(n)$,亦即

$|A|=\Omega(f(n))=\omega(n)$

则问题B也不会低于这个复杂度下界,亦即

$|B|\geq|A|=\Omega(f(n))$

实际上，若问题A可线性归约为问题B，则由后者的任一算法必然可以导出前者的一个算法。为求解问题A，可将其输入转化为问题B的输入，再调用后者的算法，将其转换为前者的输出。

因此，假若问题B具有一个更低的下界，则至少存在一个$\alpha(f(n))$的算法，于是由以上可知，问题A存在一个$\alpha(f(n))$的算法，这与问题A的已知下界不符。

为运用线性归约问题B的下界，须经历以下步骤：

  • 找到难度已知的问题A
  • 证明问题A可归约为问题B

证明有序向量唯一化的最低复杂度为nlogn

作为参照，考查所谓元素的唯一性问题(element uniqueness,简称EU)A:对于任意n个实数，判定其中是否有重复者，无序向量唯一化为难度待界定的问题B，简称为UNIQ

作为EU问题的输入，任意n个实数可在线性时间内组织为一个无序向量，从而转换为UNIQ问题的输入，另一方面，一旦得到UNIQ的问题输出(即去重以后的向量)，只需线性时间核对向量的规模是否仍然为n，即可判定原实数中是否存在重复者。

EU问题具有$\Omega(nlogn)$的复杂度下界，故以上所给的$nlogn$已属最优。