有序向量

我就是我 2023-07-14 10:36 12阅读 0赞

### 有序向量全文不少于6000字，请认真对待，可关注我哦 ###

*   *  判断向量的有序性
     *  唯一化
     *   *  低效算法
         *  高效算法
     *  有序向量的查找
     *   *  接口
         *  二分查找
         *   *  原理
             *  评估查找算法的性能
         *  fibonacci查找
         *  二分查找的改进
         *  插值查找（Interpolation Search）
         *   *  复杂度分析：
             *  可行性分析：
     *  排序
     *   *  冒泡排序
         *   *  优化
         *  归并排序
         *   *  二路归并的基本实现：
             *  对代码的解释：
             *  进一步优化：

## 判断向量的有序性 ##

template <typedef T>  //返回逆序相邻元素对的个数
    int Vector<T>::disordered()const{
        
        int n = 0;  //计数器
        for(int i = 1; i<_size; i++){
        
            n+=(_elem[i-1] > _elem[i]);
            return n;  //向量有序当且仅当n = 0
        }
    }

## 唯一化 ##

在有序向量中，重复的元素必然相互紧邻构成一个区间。因此每个区间只需保留单个元素即可。

### 低效算法 ###

为了与无序向量的唯一化以示区别，我们把原来的deduplicate（）换成有序向量的uniquify() 。  
从首元素开始，从前往后逐一比对各对相邻元素，若雷同则删除后者。

template <typedef T> int Vector<T>::uniquify(){
        
        int oldSize = _size;
        int i = 0;
        while(i < _size-1){
          //从前往后逐一比对各对相邻元素，若雷同则删除后者
            (_elem[i] == _elem[i+1] ? remove(i + 1) : i++; 
        }
        return oldSize - _size;  // 返回元素数量的减小量，即向量规模的变化量
    }  //其中_size的变化，由remove()隐式地完成

复杂度分析：  
运行时间主要取决于while循环，次数总计\_size - 1 = n-1  
最坏情况下：每次都调用remove()函数，（remove是会把其删除，把后面的元素往前移动一位），耗时O(n-1) ~ O(1)；累计O(n^2)。  
所以与之前无序向量的deduplicate()竟然复杂度相同！！！  
所以这个算法简直是个笑话，完全没把有序性发挥好！！！

### 高效算法 ###

因为本来就要删除掉重复的元素我还傻傻的把那些可以一次全移动到位的给分那么多次来移，所以低效啊！  
那么我们可以直到遇到不一样、不重复的元素时，再移动，而且完全不需要调用删除函数，可以直接移动覆盖，而且没必要每次移动都把后面的元素全移动，仅需要把当前不一样的这个元素移动到前面的尾部进行覆盖。

template <typedef 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)的时间

## 有序向量的查找 ##

在无序向量中我们的查找函数用的是find(e, lo, hi)函数，从向量的一端开始搜索，直到找到匹配的那个元素，或者移动到另一端的下一位，返回值都是秩或哨兵的位置。  
而有序向量中我们用search(e, lo, hi)函数来表示查找(仍然是从lo到hi 左闭右开区间里寻找特定元素e)，以示区别。

### 接口 ###

template <typedef T> 
    int Vector<T>::search(T const & e, Rank lo, Rank hi) const{
        
        return (rand() % 2)?  //按各50%的概率随机选用
            binSearch(_elem, e, lo, hi)  //二分查找
            : fibSearch(_elem, e, lo, hi);  //fibonacci查找算法
    }

### 二分查找 ###

#### 原理 ####

在有序向量V中插入元素e并使之保持有序：V.insert(V.seasrch(e)+1,e);  
平均和最坏复杂度都是O(n)。

template <typedef T>  //在有序向量区间[lo , hi)内查找元素e
    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;
            else if(A[mi] < e)
                lo = mi+1;
            else 
                return mi;
        }
        return -1;  //查找失败
    }

#### 评估查找算法的性能 ####

查找长度（search Length）：关键码的比较次数。  
通常需要分别针对成功；与失败查找，从最好、最坏、平均等角度评估。  
二分的成功和失败的平均查找长度均大致为O(1.5logn)。  
![语义][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]

### fibonacci查找 ###

因为二分查找转向左右支前的关键码分别用1次比较和2次比较，即比较次数不等，而递归深度却相同。  
若能通过递归深度的不均衡，对转向成本的不均衡进行补偿，平均查找长度应能进一步缩短。  
由此我们引入斐波那契查找。  
而斐波那契查找实质上与二分查找的区别仅仅在于选取得middle分割点不同，二分查找取得是大致中点处，使得每次留下1/2的序列；而fibonacci查找是按照黄金分割比例切分：mi = lo + fib.get() - 1;

template <typedef T>
    static Rank fibSearch(T* A, T const & e, Rank lo, Rank hi){
        
        Fib fib(hi - lo);  //用O(logn) = O(log(hi - lo))时间创建Fib数列
        while (lo < hi){
        
            while (hi - lo < fib.get())
                fib.prev();
            Rank mi = lo + fib.get() - 1;
            if (e < A[mi]) 
                hi = mi;
            else if (A[mi] < e)
                lo = mi + 1;
            else
                return mi;
        }
        return -1;  //查找失败
    }

Fibonacci查找的平均查找长度（ASL）,在常系数的意义上优于二分查找。  
黄金分割数： 0.6180339… 查找长度系数为1.44.420

### 二分查找的改进 ###

思路：  
![改进][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 1]  
代码实现：

template <typedef 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,查找区间仅含一个元素A[lo]
        return (e == A[lo]) ? lo : -1;  //返回命中元素的秩或者-1
    }

上述的均不满足语义，符合语义的方式如下（每次只进行一次比较）：

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)
        }  //出口时，A[lo = hi]为大于e的最小元素
        return --lo;  //故lo - 1即不大于e的元素的最大秩
    }

### 插值查找（Interpolation Search） ###

均匀独立的随机分布，则\{lo, hi)内各元素应大致按照线性趋势增长。  
所以每次设置middle 时可以动态的猜测轴点mi，极大的提高收敛速度。  
(mi - lo) / (hi - lo)约等于(e - A\[lo\]) / (A\[hi\] - A\[lo\]) ,所以推出：  
**mi = lo + (hi - lo) \* (e - A\[lo\]) / (A\[hi\] - A\[lo\])**  
![邓俊辉先生的课堂][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 2]

#### 复杂度分析： ####

最坏情况： O(hi - lo) = O(n)  
平均而言的查找成本：每经一次比较，n缩至n^(1/2) 。  
故为O(loglogn) ，甚至比O(logn)小得多  
如果说二分查找是对值每次折半（logn），那么  
插值查找的实质其实是对二进制位宽度来二分查找(loglogn)。

#### 可行性分析： ####

当查找区间宽度极大或者比较操作成本极高时才会采用插值查找，因为通常的优势并不明显，而且易受小扰动的干扰和“蒙骗”（可能会在一个小区间里转悠很久），另一方面，引入乘法和除法后成本会比较高。

所以比较可行的方法是：**首先通过插值查找，将查找范围缩小到一定的范围，然后再进行二分查找。**  
即： 大规模：插值查找；  
中规模：折半查找、  
小规模：顺序查找。  
Yeah! Perfect!

## 排序 ##

template <typedef 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 <typedef T>
    void Vector<T>::bubbleSort(Rank lo, Rank hi){
        
        while (!bubble(lo, hi--));  //逐趟做扫描交换，直至全序
    }
    template <typedef 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;  //返回有序标志
    } //乱序限于[0, n^(1/2))时，仍需O(n^(3/2))时间

#### 优化 ####

为了避免遇到一个后缀是已排好序的，我们还向上面那样一个个比较，我们可以多加一个判断，来实现算法的优化，将算法时间复杂度降至O(n)。

template <typedef T>
    void Vector<T>::bubbleSort(Rank lo, Rank hi){
        
        while (lo < (hi = bubble(lo, hi))); //逐趟扫描交换，直至全序 
    }
    template <typedef 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;  //返回最右端的逆序对位置
    }  //前一版本中的逻辑型标志sorted,改为秩last

### 归并排序 ###

解递推式： T(n) = 2 \* T(n/2) + O(n)  
得到：O(nlogn)

template <typedef 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);  //归并
    }

#### 二路归并的基本实现： ####

template <typedef T> 
    void Vector<T>::merge(Rank lo, Rank mi, Rank hi){
        
        T* A = _elem + lo;  //合并后的向量[0,hi - lo) = _elem[lo, hi)
        int lb = mi-lo;
        T* B = new T[lb];  //前子向量B[0, lab) = _elem[lo, mi)
        for(Rank i = 0; i< lb; B[i] = A[i++]);  //复制前子向量B
        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) && (lc <= k || (B[j] <= C[k])))
                A[i++] = B[j++];  //C[k]已无或不小
            if((k < lc) && (lb <= j || (C[k] < B[j])))
                A[i++] = C[k++];  //B[j]已无或更大
        }  //该循环实现紧凑，但就效率而言，不如拆分处理
        delete [] B;  //释放临时空间B
    }

*能看懂代码的话，可以跳过这一段：*

#### 对代码的解释： ####

A、B、C

> 其中A是\_elem起始于lo的向量；B是新申请的一块用于缓存左侧子向量的空间，将A中的lo到mi之间的所有元素一一复制到B中完成B的初始化。想要将C中存储从mi到hi的元素，我们可以直接T\* C = \_elem +mi；即将\_elem中mi（包括mi）之后的放入右侧子向量C中（C中的k一定不会在i的左侧，因为当i<mi时，显然k在其右侧；当i>=mi时，A中i之前的总数等于B的元素总数加上i-mi，而哪怕前mi项元素全部都是B贡献的，那些多余的来自C也足以保证C中的k恰好不在i的左侧，所以这样对C不另开空间是可行的安全的，不会发生覆盖的）。

循环

> 循环中其实就是每次都比较两个子向量中当前的首元素，取出其中更小的那个放入A中。所以j,k来标定首元素，最初始情况下，分别指向B和C的第一个元素。在随后，每当有一个元素转移到A中，那么来自的那个子向量的j或k便会自加1，指向下一个新的首元素。而A中每次纳入的元素是用i来指示的，所以每当有元素要进入A中，i自加1。

两个分支

> 循环中的两个判断分支：拿B中当前首元素更小的来说，首先要求B中j所指向的元素还在范围内，是合法的，即j <lb;当k越界（这时也可以假想C的末尾多一个值为正无穷的哨兵），即C中的元素都用完了（已经都移动到A中了） 或者 j，k都没越界但B\[j\]<= C\[k\]时都是要将B中当前元素移动到A中的（这里我们利用了短路的特性，如果&&前面的判断不满足，则直接出分支进入下一个分支，这样就避免了&&后面的判断中访问元素越界，造成程序运行错误）。

#### 进一步优化： ####

仔细理一理过程不难发现，如果但i增加到某一处，B\[j\]要超界失去意义时，剩下的C中的元素本身就是在A中的，完全可以不再进行复制移动操作。

精简实现：  
在实现上也就是不去考虑在C中k的越界，只用B结束，我们就结束循环。  
而且在分支中不用再去判断j是否越界，因为在循环条件里已经判断。

for(Rank i = 0, j = 0, k = 0; (j < lb)  ;){
        
        if((k < lc) &&  (c[k] < B[j]))
            A[i++] = C[k++];
        if( lc <= k || (B[j] <= C[k]))
            A[i++] = B[j++];
    }  //交换循环体内两句的次序，删除冗余逻辑

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]: /images/20230529/fd9832472e8840e6a44bf961389f7b94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 1]: /images/20230529/516ccba0df0143b89a63894264756406.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 2]: /images/20230529/e25e3665213c47e08799b595e85febd0.png