从无序到有序

我们可以看到在无需向量的算法中，所需要的算法时间复杂度都不是特别理想，因此我们引入了排序算法，将无需向量整理成为有序向量。本节中，你将体验到“秩序”的力量，并见证一个非常高效，厉害的算法。

有序的好处

如果你的士兵按照一定的顺序排列好，你对他们进行点名、布置小队任务什么的，当然会比乱排的要方便，对向量中的元素也是如此，当它们按照从小到大的顺序排列好，你会发现很多算法都要方便不少。

有序性甄别

前面我们提到，无需向量和有序向量的操作接口是不一样的，所以在确定要使用什么接口之前，我们要对向量进行一个甄别，判断他们是不是已经有序。
该算法与气泡排序算法原理相同：

template<typename T>
int Vector1<T>::disordered() const
{
	int n;
	for (int i = 1; i < _size; i++)
	{
		if (_elem[i-1]>_elem[i])
		{
			n++;
		}
	}
	return n;
}

唯一化

向量操作算法中，最令我震撼和佩服的一个。
在有序向量中，我们可能会遇到值相等的元素相邻地进行排列，我们会想要将这些重复的元素删除，然而在有序向量中，把这些重复元素删除将比在无需向量中容易。
对于无需向量中的唯一化算法我将不再赘述，我们直接来看更为高效的这一种：

这幅图片很直观地展示出了我们将要采取的策略——很粗暴很直接：直接忽略那些重复的元素，把和当前元素互异的元素直接拿到当前元素的后面。

这真的是一种非常高明的算法，我们需要消耗时间复杂度的只有把所有元素全部遍历一遍而已！所需的时间复杂度仅仅为O(n)！相对于之前的O(n^2)可以说是优化了很多了！

下面来看看具体代码：

template<typename T>
int Vector1<T>::uniquify()
{
	Rank i = 0, j = 0;
	while (++i<_size)
	{
		if (!_elem[j]==_elem[i])
		{
			_elem[++j] = _elem[i];
		}
	}
	_size = ++j;
	shrink();
	return i - j;
}

下面对这段代码进行一个简单的说明：
我们从初始位置开始(记为j)，先把后面的每个元素与之进行比较，由于向量是有序的，所以假设后面的N个元素都和该元素相等，这些元素我们都直接略过，直到扫描到位置i，碰到了第一个和j位置不一样的元素，此时我们的计数标i不用动，把i这个位置的元素直接拉到前面去，位置就为j+1了，然后以j+1作为比较元素，i继续往后扫描，这样一趟下来，就只需要O(n)复杂度啦。

查找

在有序向量中，我们有两种查找算法：二分查找和Fibnacci查找.

二分查找

二分查找我们采用最传统的分而治之的思想

template<typename T>
Rank Vector1<T>::binSearch(T* A, T const& e, Rank low, Rank high)
{
	while (1<high-low)  //当子区间长度减少到1之前一直进行
	{
		Rank middle = (high - low) >> 1; //计算区间中点
		(e < A[middle]) ? high = middle : low = middle; //进行比较并确立新的区间端点

	}
	return (e == A[low] ? low : -1); //查找失败返回-1
}

整个算法的时间复杂度还是O(logn)。

归并排序

template<typename T>
void Vector1<T>::merge(Rank low, Rank middle, Rank high)
{
	T* A = _elem + low;
	int 1b = middle - low;
	T* B = new T[1b];
	for (Rank i = 0; i < 1b; B[i] = A[i++]);
	int lc = high - middle;
	T* C = _elem + middle;
	//以上都是构建、复制向量的过程
	for (int i = 0,j=0,k=0; (j<1b)||(k<lc);)
	{
		if ((j < 1b) && (!(k < 1c) || (B[j] <= C[k])))
		{
			A[i++] = B[j++];
		}
		if ((k < 1c) && (!(j < 1b) || (C[k] < B[j])))
		{
			A[i++] = C[k++];
		}
	}
}

采用的也是最经典的分治策略：先分组复制数组，得到前后子向量B和C，然后将这两者中的小者续至A末尾。

不难得出时间复杂度为O(n)。

总结

向量到这里就结束了，我们得到了向量的模板类，在今后的学习路程中我们还会用到我们得到的向量模板类去构建别的数据结构。