2.4 有序向量

相邻逆序对的数量，可以度量向量的逆序程度

template <typename T> // 返回相邻逆序对数量
int Vector<T>::disordered() const {
    int n = 0; // 计数器
    for (int i = 1; i < _size; i++) // 逐一检查相邻元素对
        n += (_elem[i - 1] > _elem[i]);  // 若逆序则计数
    return n = 0; // 当且仅当n = 0时，向量有序
} // 若仅判断是否有序，则首次出现逆序对时即可返回

唯一化
在有序向量中，重复元素必然相邻构成一个区间，因此每个区间保留单个元素即可

template <typename T>
int Vector<T>::uniquify() { // 低效算法
    int oldSize = _size;
    int i = 0; // 从首元素开始，逐一对比相邻元素
        (_elem[i] == _elem[i + 1]) ? remove(i + 1) : i++; // 若相同，则删除后者，否则转至后一元素
    return oldSize - _size; // 向量规模变化量，即删除元素数量
} // _size减小，由remove()隐式完成

同一元素作为被删除元素的后继多次前移，导致低效；若以重复区间为单位，批量删除重复元素，可以提高性能。

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; // 向量规模变化量，即删除元素数量
} // 通过remove(lo, hi)批量删除，仍无法高效完成

二分查找

template <typename T> // 查找算法统一接口，0 <= lo < hi <= _size
Rank Vector<T>::search(T const & e, Rank lo, Rank hi) const {
    return (rand() % 2) ? binSearch(_elem, e, lo, hi) : fibSearch(_elem, e, lo, hi); // 按各50%概率随机选用二分查找算法或Fibonacci查找算法
}

至少应易于有序向量自身维护V.insert(1 + V.search(e), e)
即使失败也应给出新元素适当的插入位置
若允许重复元素则每一组也需按其插入次序排列
语义约定：
在有序向量区间[lo, hi)中，确定不大于e的最后一个元素
若-∞ < e < v[lo]，则返回lo - 1（左侧哨兵）
若v[hi - 1] < e < +∞，则返回hi - 1（末元素，即右侧哨兵左邻）
原理：
以任一元素x = S[i]为界，可将待查找区间分为3部分，S[lo, mi) <= S[mi] <= S(mi, hi)
只需将目标元素e与x比较，即可分3种情况进一步处理
(1) e < x，若e存在则必属于左侧子区间S[lo, mi)，可递归深入
(2) x < e，若e存在则必属于右侧子区间S(mi, hi)，可递归深入
(3) e = x，在此处命中，随即返回
二分策略，轴点总是取作中点，每经过至多两次比较，或命中，或将问题规模缩减一半

template <typename T> // 在有序向量区间[lo, hi)内查找元素e
static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
    while (lo < hi) { // 每次迭代可能需要两次比较判断，有3个分支
        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; // 查找失败
}

Fibonacci查找
二分查找转向左右分支前的关键码比较次数不等，而递归深度相同
若通过递归深度不均衡，对转向成本不均衡进行补偿，平均查找长度(search length)可进一步缩短
若设n = fib(k) - 1，则可取mi = fib(k - 1) - 1，前后子向量长度分别为fib(k - 1) - 1与fib(k - 2) - 1

template <typename T> // 0 <= lo <= hi <= _size
static Rank fibSearch(T* A, T const & e, Rank lo, Rank hi) {
    Fib fib(hi - lo); // 创建Fibonacci数列
    while (lo < hi) {
        while (hi - lo < fib.get()) fib.prev(); // 向前顺序查找，确定形如Fib(k) - 1的轴点
        Rank mi = lo + fib.get() - 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; // 查找失败
}

通用策略：对于任意A[0, n)，总是选取A[λn]作为轴点，0 <= λ < 1

二分查找左右分支转向代价不平衡，可通过每次迭代（或每个递归实例）仅1次关键码比较而解决，所有分支仅有2个方向
轴点mi取作中点，查找每深入一层，问题规模缩减一半
若e < x，则e存在必属于左侧子区间S[lo, mi)，可递归深入
若x <= e，则e存在必属于右侧子区间S[mi, hi)，可递归深入
当且仅当元素数目hi - lo = 1时，判断该元素是否命中

template <typename T> static Rank binSearch(T* A, T const & e, Rank lo, Rank hi) {
    while (1 < hi - lo) { // 有效查找区间宽度缩短至1时，算法终止
        Rank mi = (lo + hi) >> 1; // 以中点为轴点，经比较后确定深入
        (e < A[mi]) ? hi = mi : lo = mi; // [lo, mi)或[mi, hi)
    } // 出口时hi = lo + 1，查找区间仅1个元素A[lo]
    return (e == A[lo]) ? lo : -1; // 返回命中元素的秩或-1
}

二分查找与Fibonacci查找均未严格实现search()接口的语义约定（返回不大于e的最后一个元素）

template <typename T> static Rank binSearch(T* A, T const & e, Rank lo, Rank hi) {
    while (lo < hi) { // 不变性，A[0, lo) <= e < A[hi, n)
        Rank mi = (lo + hi) >> 1; // 以中点为轴点，经比较后确定深入
        (e < A[mi]) ? hi = mi : lo = mi + 1; // [lo, mi)或[mi, hi)
    } // 出口时，A[lo = hi]为大于e的最小元素
    return --lo; // lo - 1即不大于e的元素的最大秩
}

(1) 待查找区间宽度缩至0而非1时，算法结束
(2) 转入右侧子向量时，左边界取mi + 1而非mi
(3) 无论成功与否，返回的秩严格符合接口的语义约定

冒泡排序

template <typename T> // 排序器，统一入口
void Vector<T>::sort(Rank lo, Rank hi) { // 区间[lo, hi)
    switch (rand() % 5) {
        case 1: bubbleSort(lo, hi); break; // 冒泡排序
        case 2: selectionSort(lo, hi); break; // 选择排序
        case 3: mergeSort(lo, hi); break; // 归并排序
        case 4: heapSort(lo, hi); break; // 堆排序
        default: quickSort(lo, hi); break; // 快速排序
    }
}

template <typename T> void Vector<T>::bubbleSort(Rank lo, Rank hi) {
    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; // 返回有序标记
}

template <typename T> void Vector<T>::bubbleSort(Rank lo, Rank hi) {
    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; // 返回最右侧逆序对标记
}

归并排序

template <typename T> void Vector<T>::mergeSort(Rank lo, Rank hi) { // [lo, hi)
    if (hi - lo < 2) return; // 单元素区间自然有序
    int mi = (lo + hi) >> 1; // 以中点为界
    mergeSort(lo, mi); // 对前半段排序
    mergeSort(mi, hi); // 对后半段排序
    merge(lo, mi, hi); // 归并
}

二路归并(2-way merge)：将两个有序序列合并为一个有序序列，S[lo, hi) = S[lo, mi) + S[mi, hi)

template <typename T> void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {
    T* A = _elem + lo; // 合并后向量A[0, hi - lo) = _elem[lo, hi)
    int b = mi - lo;
    T* B = new T[b]; // 前子向量B[0, b) = _elem[lo, mi)
    for (Rank i = 0; i < b; B[i] = A[i++]); // 复制前子向量B
    int c = hi - mi;
    T* C = _elem + mi; // 后子向量C[0, c) = _elem[mi, hi)
    for (Rank i = 0, j = 0, k = 0; (j < b) || (k < c);) { // B[j]与C[k]中较小者转至A末尾
        if ((j < b) && (c <= k || (B[j] <= C[k])))
            A[i++] = B[j++];
        if ((k < c) && (b <= j || (C[k] < B[j])))
            A[i++] = C[k++];
    } // 该循环实现紧凑，但效率不如拆分处理
    delete [] B; // 释放临时空间B
}