/******************************************************************************************
* Data Structures in C++
* ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
* Junhui DENG, deng@tsinghua.edu.cn
* Computer Science & Technology, Tsinghua University
* Copyright (c) 2003-2021. All rights reserved.
******************************************************************************************/
#include "Vector.h"
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; //释放原空间
}
template <typename T>
void Vector<T>::shrink() //装填因子过小时压缩向量所占空间
{
if ( _capacity < DEFAULT_CAPACITY << 1 ) return; //不致收缩到DEFAULT_CAPACITY以下
if ( _size << 2 > _capacity ) return; //以25%为界
T* oldElem = _elem; _elem = new T[_capacity >>= 1]; //容量减半
for ( int i = 0; i < _size; i++ ) _elem[i] = oldElem[i]; //复制原向量内容
delete [] oldElem; //释放原空间
}
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; //返回秩
}
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即命中元素的秩
}
template <typename T> void Vector<T>::traverse ( void ( *visit ) ( T& ) ) //借助函数指针机制
{
for ( int i = 0; i < _size; i++ )
visit ( _elem[i] );
} //遍历向量
template <typename T> template <typename VST> //元素类型、操作器
void Vector<T>::traverse ( VST& visit ) //借助函数对象机制
{
for ( int i = 0; i < _size; i++ )
visit ( _elem[i] );
} //遍历向量
template<typename T> void Vector<T>::swap(T &e1, T &e2) {
int temp;
temp = e1;
e1 = e2;
e2 = temp;
}
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; //返回有序标志
}
template<typename T> void Vector<T>::bubbleSort(Rank lo, Rank hi) {
while ( !bubble(lo, hi--) ) ; //逐趟做扫描交换，直至全序
}
template<typename T> void Vector<T>::merge(Rank lo, Rank mi, Rank hi)
{//有序向量的归并，以mi为界，各自有序的子向量[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; i++)
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 ;
}
template<typename T> void Vector<T>::mergeSort(Rank lo, Rank hi) { //向量归并排序
if (hi - lo < 2) return ;
int mi = (lo + hi) >> 1 ; //以中点为界
mergeSort(lo, mi);
mergeSort(mi, hi);
merge(lo, mi, hi); //分别对前后半段排序，然后归并
}
template <typename T> //向量选择排序
void Vector<T>::selectionSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
while ( lo < --hi )
swap ( _elem[ maxItem ( lo, hi ) ], _elem[ hi ] ); //将[hi]与[lo, hi]中的最大者交换
}
template <typename T>
Rank Vector<T>::maxItem ( Rank lo, Rank hi ) { //在[lo, hi]内找出最大者
Rank mx = hi;
while ( lo < hi-- ) //逆向扫描
if ( _elem[ hi ] > _elem[ mx ] ) //且严格比较
mx = hi; //故能在max有多个时保证后者优先，进而保证selectionSort稳定
return mx;
}
template<typename T> void Vector<T>::sort(Rank lo, Rank hi) {
//switch (random() % 2) { //随机选择排序算法，可根据问题的特点灵活选取或扩充
// case 1 : bubbleSort(lo,hi) ; break ; //起泡排序
// case 2 : mergeSort(lo,hi) ; break ; //归并排序
bubbleSort(lo, hi); //起泡排序
mergeSort(lo, hi); //归并排序
selectionSort(lo, hi); //选择排序
}
