0x05 排序

· · 个人记录

排序的分类

第一大类：基于比较的排序算法

第二大类：基于数值的排序算法

  1. 与数据范围有关：计数排序，基数排序，桶排序

离散化

实现方式：

  1. 先用lsh数组存下真实值和在原数组中的位置
  2. 将lsh数组以真实值的大小排序
  3. 将相同的真实值用同一个数代替（即去重）
  4. 用mp数组记录a[i]离散化后的值
int n,mp[2000010],a[2000010];
struct mapping{
    int v,i;
    bool operator <(mapping x)const{
        return v<x.v;
    }
}lsh[2000010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        lsh[i]=(mapping){a[i],i};//将真实值和在a数组中的位置塞入lsh数组
    }std::sort(lsh+1,lsh+n+1);
}

这样我们就完成了1.2.两步

第三步去重，可以用STL的unique函数，也可以自己写

unique只能去除相邻重复项，因此如果要完全去重，需要原序列是有序的，复杂度O(n)

len=unique(lsh+1,lsh+n+1)-lsh-1;
//unique会把所有重复值放到数组末尾，不会删掉，因此需要得到新的数组长度
//unique的返回值指向的是去重后容器中不重复序列的最后一个元素的下一个元素，因此要减1

//用自己的写法
int k=0;
for(int i=1;i<=n;i++){
    if(lsh[i].v!=lsh[i-1].v)k++;
    mp[lsh[i].i]=k;
}//mp是a[i]离散化后的值

如果用unique的话，是不能直接得到a[i]对应的离散化值的，或者如果我们不知道i，只知道真实值为x，怎么办呢？

众所周知，STL大法好，既然前面用了STL的unique，后面也不妨用STL的lower_bound()，查询lsh数组中第一个大于等于x的数的位置即可

//对应unique做法
lower_bound(lsh+1,lsh+n+1,(mapping){x,0})-lsh

//对应手写做法，不用先unique
mp[lower_bound(lsh+1,lsh+n+1,(mapping){x,0})->i]

这里因为lsh是一个mapping类型的数组，所以把x捆绑在一个mapping类型的变量里输入函数查找

中位数

一般地，若一个序列长度为n：

动态维护中位数：对顶堆算法

建立一个大根堆和一个小根堆

维护以下性质：

  1. 序列中从小到大排名为1~n/2的整数存储在大根堆中

  2. 序列中从小到大排名为n/2+1~n的整数存储在小根堆中

这样可以保证小根堆的堆顶就是中位数（n为偶数时在中间两个数范围内，一般也是最优）

加入一个数x时：

加入完毕后再次维护对顶堆性质即可

归并排序求逆序对个数

逆序对：若 i<j 且 a_i>a_j，则构成一个逆序对

归并排序的原理：将原数组分成l~mid,mid+1~r两份，将两部分分别排序后合并为l~r的有序数列

因此可知，归并排序合并时，左区间和右区间已经有序，那么用双指针 i,j 扫描时，如果出现 a_i<a_j，那么 a_j\in (a_{i-1},a_i)，因此 a_j小于 a_i 至 a_{mid} 的所有值，所以逆序对个数统计多增加mid-i+1个。因此每一个统计的都一定是逆序对，充分性得证

又因为每个逆序对都一定会在某一步中属于两个不同的区间，这时就会被统计进答案，所以每一个逆序对都会被统计进答案，必要性得证

最后还有一点，因为统计过的逆序对在进行合并之后都会消失，所以不会重复统计同一个逆序对。

Q.E.D.