0001 using Rank = unsigned int; //秩
0002 #define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）
0003 
0004 template <typename T> class Vector { //向量模板类
0005 protected:
0006    Rank _size; Rank _capacity;  T* _elem; //规模、容量、数据区
0007    void copyFrom ( T const* A, Rank lo, Rank hi ); //复制数组区间A[lo, hi)
0008    void expand(); //空间不足时扩容
0009    void shrink(); //装填因子过小时压缩
0010    bool bubble ( Rank lo, Rank hi ); //扫描交换
0011    void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法
0012    Rank maxItem ( Rank lo, Rank hi ); //选取最大元素
0013    void selectionSort ( Rank lo, Rank hi ); //选择排序算法
0014    void merge ( Rank lo, Rank mi, Rank hi ); //归并算法
0015    void mergeSort ( Rank lo, Rank hi ); //归并排序算法
0016    void heapSort ( Rank lo, Rank hi ); //堆排序（稍后结合完全堆讲解）
0017    Rank partition ( Rank lo, Rank hi ); //轴点构造算法
0018    void quickSort ( Rank lo, Rank hi ); //快速排序算法
0019    void shellSort ( Rank lo, Rank hi ); //希尔排序算法
0020 public:
0021 // 构造方法
0022    Vector ( Rank c = DEFAULT_CAPACITY ) //容量为c的空向量
0023    { _elem = new T[_capacity = c]; _size = 0; }
0024    Vector ( Rank c, Rank s, T v ) //容量为c、规模为s、所有元素初始为v；s<=c
0025    { _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); }
0026    Vector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } //数组整体复制
0027    Vector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //区间
0028    Vector ( Vector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //向量整体复制
0029    Vector ( Vector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //区间
0030 // 析构方法
0031    ~Vector() { delete [] _elem; } //释放内部空间
0032 // 只读访问接口
0033    Rank size() const { return _size; } //规模
0034    bool empty() const { return !_size; } //判空
0035    Rank find ( T const& e ) const { return find ( e, 0, _size ); } //无序向量整体查找
0036    Rank find ( T const& e, Rank lo, Rank hi ) const; //无序向量区间查找
0037    Rank select( Rank k ) { return quickSelect( _elem, _size, k ); } //从无序向量中找到第k大的元素
0038    Rank search( T const& e ) const //有序向量整体查找
0039    { return ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }
0040    Rank search ( T const& e, Rank lo, Rank hi ) const; //有序向量区间查找
0041 // 可写访问接口
0042    T& operator[] ( Rank r ); //重载下标操作符，可以类似于数组形式引用各元素
0043    const T& operator[] ( Rank r ) const; //仅限于做右值的重载版本
0044    Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符，以便直接克隆向量
0045    T remove ( Rank r ); //删除秩为r的元素
0046    Rank remove ( Rank lo, Rank hi ); //删除秩在区间[lo, hi)之内的元素
0047    Rank insert ( Rank r, T const& e ); //插入元素
0048    Rank insert ( T const& e ) { return insert ( _size, e ); } //默认作为末元素插入
0049    void sort ( Rank lo, Rank hi ); //对[lo, hi)排序
0050    void sort() { sort ( 0, _size ); } //整体排序
0051    void unsort ( Rank lo, Rank hi ); //对[lo, hi)置乱
0052    void unsort() { unsort ( 0, _size ); } //整体置乱
0053    Rank dedup(); //无序去重
0054    Rank uniquify(); //有序去重
0055 // 遍历
0056    void traverse ( void (* ) ( T& ) ); //遍历（使用函数指针，只读或局部性修改）
0057    template <typename VST> void traverse ( VST& ); //遍历（使用函数对象，可全局性修改）
0058 }; //Vector