[数据结构与算法]洛谷题单 Part2.2 排序算法（十种常见的排序算法）

瞄了一眼题 发现都是直接$sort$就可以过的题 所以我决定从头学一下排序算法 不要浪费这个复习排序算法的机会

$0.$排序的介绍

排序算法 顾名思义就是把无序变为有序 对象可以是数组 或者链表等 常见的排序算法大概有10种左右 如下图


图片来自菜鸟教程
那么我们一个一个来

$1.$各种排序的原理及实现

冒泡排序

冒泡排序的本质是交换 对于每个数 与他相邻的数作比较 如果左边的数大(小) 那就进行交换 否则不交换 那么这样操作一轮下来 最右侧的数一定是最大(小)的 多次进行操作后得到的是一个升(降)序的一个排列 因为这样一个一个往上窜的形式很像冒泡泡 所以被称为冒泡排序

时间复杂度

$O(n^2)$ 最好情况是一个数组本身就是有序的 这时的时间复杂度是$O(n)$

上代码(我写的是升序排列)↓

选择排序

选择排序我感觉是一种比较像人类肉眼排序用的方法 非常简单粗暴 从数列里找到最小(大)的数 将其放在第一位 再从剩余数列中找到最小(大)的数 将其放在第二位 以此类推 最后会排除一个升(降)序的数组

时间复杂度

$O(n^2)$

上代码↓

插入排序

插入排序可以形象地理解为码牌的过程 每抓到一张牌 要把它插入手里的牌堆中
每更新一个数时 从后向前（或者从前向后）找到这个数应该在有序数组的位置

时间复杂度

$O(n^2)$ 最优情况是数组有序 线性复杂度$O(n)$
上代码↓

希尔排序

在希尔排序出现之前，大家普遍认为排序算法的复杂度不会优于$O(n^2)$ 直到$D.L.Shell$在$1959$年发布了以自己命名的这个算法
希尔排序总体来说是对插入排序的一个优化改良版本 注意到插入排序的以下性质

$(1)$如果插入排序操作一个有序数组 那么他的时间复杂度将会达到惊人的$O(n)，$而冒泡排序和选择排序都做不到，我们称对有序数组的插入排序为特殊插入排序，而对于每个长度为$1$的数组 显然为特殊插入排序
$(2)$简单插入排序每次只能将每一个元素移动一次 效率较低

针对第二种性质 希尔做出了以下优化 每次对间隔为$gap$的元素进行普通插入排序 然后缩小$gap，$对新的$gap$进行一样的操作 即对间隔为$gap$的元素进行普通插入排序。最后$gap$为$1$的时候就是插入排序 但是由于这个数组已经部分有序了 所以进行插入排序的步骤会比直接插入排序的步骤少很多。其中称$gap$为增量，$gap$组成的序列为增量序列。因其是逐次递减的，故希尔排序也被称为增量递减排序。希尔使用的增量序列是$1,2,4,8,...，$即$2^k，k=1,2,3,...，$,一般称其为希尔增量。
希尔排序的缺点：希尔排序不是特别稳定 最坏时间复杂度还是$O(n^2)$
此外 希尔排序还可能会改变相等元素的位置关系，例如这个数组$a[]=0,1,4,3,3,2,5，$在$gap=2$的时候，对$0,4,3,5$进行普通插入排序时，将两个$3$的位置互换了

时间复杂度

希尔排序的时间复杂度和选取的增量序列有关
$Shell$增量$(Shell,1959):1,2,4,8,...，$即$2^k，k=1,2,3,...，$最坏时间复杂度$O(n^2)$。
$Hibbard$增量$(Hibbard,1963)：1,3,7,15,...，$即$2^k?1，k=1,2,3,...，$最坏时间复杂度$O(n^{3/2})$。
$Knuth$增量$(Knuth,1971)：1,4,13,40,...，$即$(3^k?1)/2，k=1,2,3,...，$最坏时间复杂度$O(n^{3/2})$。
$Sedgewick$增量$(Sedgewick,1982):1,8,23,77,281，即4^k+3?2^{(}k?1)+1($最小增量1直接给出$)，k=1,2,3,...，$最坏时间复杂度$O(n^{4/3})$。
由此可见 选择正确的增量序列 可以将最坏时间复杂度打破$O(n^2)$的次元壁

原理

先说一个大家都会的概念 逆序数（打开我的线代教材
定义：在一个排列中，若一个较大的数排在一个较小的数之前，则称这两个数构成一个逆序（对）。排列$j_1{j}_2...j_n$中,逆序的总个数称为该排列的逆序数。
不难发现 插入排序和冒泡排序每次只能将一对逆序对处理掉，逆序对最多为$O(n^2)，$因此最坏时间复杂度为$O(n^2)$
而希尔排序处理间隔为$gap$的逆序对，打破了相邻一对交换的固有定式思维，一次处理可以减少多个逆序对，从而让算法打破了二次方的次元壁

上代码 我们以$Sedgewick$增量做为增量序列 （最坏复杂度为$O(n^{4/3})$）

归并排序

归并排序哈哈哈 这个有故事的算法 之前初中的时候教练说我们抄代码就让我们打归并排序验证到底是不是抄的 可是考试的题和排序一点关系没有捏 老师就总说我抄代码 后来自己学了归并排序 他就开始找别的地方的毛病了哈哈
归并排序利用了分治的思想

首先 对于两个已经排好序的数组 将他们合并成一个有序的大数组所需时间为$O(n+m)$
例如 a [ ] = { 1 , 3 , 5 , 7 , 9 } , b [ ] = { 2 , 4 , 6 , 8 , 10 } , a[]=\{1,3,5,7,9\},b[]=\{2,4,6,8,10\}, a[]={1,3,5,7,9},b[]={2,4,6,8,10},要合并成一个大数组$c[]$那么我们每次判断$a、$$b$数组的第一个元素，如果$a$的小那就把$a$数组的第一个元素放入$c$中，反之则放$b$数组的第一个元素，这样到最后每个元素都被操作过一次 因此为线性复杂度。
我们称这个操作为合并

归并排序的思路就是将数组先分为$2$部分，然后将这两部分分别操作为有序数组，再将这两个数组利用上述操作线性完成排序。我们称这个操作为分割

那么如何将这两部分分别变成有序数组呢，那就是一个递归问题了，将这两个数组再分别利用分割操作分成两部分，直到某一部分长度为$2，$此时再将其分为两部分，因为数组长度为$1$一定是有序数组，所以这时可以将这两部分利用合并操作在一起，以此类推，最后得到的就是有序数组

时间复杂度

对于每个合并操作都为线性复杂度，对于分割操作需要进行$O(lo{g}_n)$次，因此时间复杂度为$O(nlo{g}_n)$

上代码

归并排序的应用

求逆序数
逆序对的定义上面给了 再复制一下
定义：在一个排列中，若一个较大的数排在一个较小的数之前，则称这两个数构成一个逆序（对）。排列$j_1{j}_2...j_n$中,逆序的总个数称为该排列的逆序数。
怎么求捏
观察合并操作
对于待操作序列$a_p,a_{p+1},...,a_m,b_q,b_{q+1},...,b_r$
如果$a_p<b_q,$因为$a，b$数组都是有序的，所以有$a_p<a_{p+1}<...<a_m;a_p<b_q<b_{q+1}<...<b_r$因此不包含关于$a_p$的逆序对
如果$a_p>b_q,$则有$a_m>a_{m?1}>...>a_{p+1}>a_p>b_q$此时关于$b_q$的逆序对共有$m?p+1$对，故逆序对数$+=m?p+1$

上题

P1908 逆序对

传送门
其实逆序对最初的做法是$O(n^2)，$利用插入排序一个一个处理
其次才是利用归并排序的$O(nlo{g}_n),$这个上面讲完了
板子题 数据比较大 得用快读 还有$ans$最大可以是$n^2，$所以要开$longlong$
直接上代码了

#include<bits/stdc++.h>
#define N 500050
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
int n,a[N],b[N];
long long ans;
void merge_sort(int l, int m, int r){
    int p=l,q=m+1,t=l;
    while(p<=m&&q<=r){
        if(a[p]>a[q])b[t++]=a[q++],ans+=m-p+1;
        else b[t++]=a[p++];
    }
    while(p<=m)b[t++]=a[p++];
    while(q<=r)b[t++]=a[q++];
    for(reg int i=l;i<=r;i++)a[i]=b[i];
}
void merge(int l, int r){
    if(l<r){
        int m=l+r>>1;
        merge(l,m),merge(m+1,r);
        merge_sort(l,m,r);
    }
}
int main(){
    read(n);
    for(reg int i=1;i<=n;i++)read(a[i]);
    merge(1,n);
    cout<<ans<<endl;
}

快速排序

与归并排序一样，快速排序也是利用分治和递归的思想
快速排序首先要找到一个主元，然后将数组分为两部分，小于主元的放在左侧，大于主元的放在右侧，然后递归地对左右两侧数组进行一样的操作

时间复杂度

与主元的选取有关

$(1)$ 主元为起始元素 每次选取当前数组第一个元素作为主轴。
优点：实现简单。
缺点：若输入是较为有序的数组，主元总是不能均匀地分割数组。若输入数组本身有序，复杂度退化到$O(n^2)。$
$(2)$主元为随机下标 每次随机选取当前数组的下标，将该下标元素作为主元。

优点：避免了主元为起始元素时对于基本有序的输入，因不能均匀分割数组导致复杂度退化的情况。
缺点：随机数的选取本身消耗一定的性能。
$(3)$主元为左中右三数居者 每次比较当前数组起始、中间和末尾三个元素的大小，大小居中者为主元。

优点：实现相对简单，且有效避免简单快排中的劣质分割。
缺点：三数取中方法消耗一定性能。
快速排序也可以与其他排序相结合，例如当元素较少时使用简单插入排序能够获得更高的排序效率。
上题

P1177 【模板】快速排序

传送门
题面说不要直接$sort$ 要自己手打快排 我打了传统快排 但是被卡了三个点 你这不有毛病吗出题人
看了眼题解有个大哥二分选主元 比$sort$还快 挺有意思 我也打打

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
int n,a[N];
void quick_sort(int l, int r){
    int mid=a[(l+r)/2],i=l,j=r;
    while(i<=j){
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j){swap(a[i],a[j]);i++,j--;}
    }
    if(l<j)quick_sort(l,j);
    if(i<r)quick_sort(i,r);
}
int main(){
    read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    quick_sort(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
}

堆排序

堆排序 顾名思义就是要用到堆这个数据结构的排序 那就浅浅说两句堆
堆是一个完全二叉树 分为两种堆 大根堆和小根堆 分别对应他的父节点大于/小于子节点
堆一般用数组进行存储，下标为$i$的结点父节点为$i/2,$左右子节点分别为$i\times 2$和$i\times 2+1$
堆的操作一般有三种
$(1)$建堆，将所有数据重新排序
$(2)$插入，将新数据插入到末端节点，然后递归进行调整
$(3)$弹出，将堆顶元素弹出，然后递归调整堆
因为堆是二叉树结构 因此每次堆已经排好序的堆插入弹出元素所需的调整时间复杂度为$O(lo{g}_n)$
现在我们用这些操作进行堆排序 只需要将数组建称堆结构 然后再依次弹出即可 时间复杂度为$O(nlo{g}_n)$
上代码

计数排序

听到这个名字你可能会感觉云里雾里，好高大上的名字配上nb的线性复杂度 你一定会以为他是什么高级算法
其实这只是在某种特定环境下的排序 我们每个人可能都无意间用到了这个算法
具体来说 就是确定了元素大小在$1?k$之间，并且这个$k$不是很大
我们新建一个数组$a[],$其中$a[i]=j$代表值为$i$的元素出现了$j$次
从而达到线性排序的目的 但是当元素较大时无法使用
上代码↓

由于后面两个算法基本不会用到 所以这里代码粘的外面的 如果有错误请xdm指正

桶排序

基于上述排序，我们考虑如果数非常大，想用类似计数排序应该怎么做，这就有了桶排序
将$n$个数据均匀地分配到$k$个桶中，对于桶中的元素再进行简单排序算法处理

时间复杂度

最优：当输入的数据可以均匀的分配到每一个桶中 此时时间复杂度为$O(n+k)$
最差：当输入的数据都被分到一个同种 此时时间复杂度为$O(n^2)$
上代码

基数排序

基数排序也是对计数排序的一个升级改良版本 操作过程如下
1.先将所有数的位数补齐，即将位数较小的数前面补上相应的零
2.将所有数的单一位按计数排序来排，这里有两种方式 分别是从高位到低位和从低位到高位
上代码

上题上题 一般在计算机竞赛里我们通常排序直接用$sort$函数 所以题一般都比较水

P1177 【模板】快速排序

传送门
上面讲了 板子题

P1059 [NOIP2006 普及组] 明明的随机数

传送门
去重，排序，小范围数据，果断计数排序$($好打脸 第一题就没$sort)$

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[110],s[1010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!s[a[i]])sum++;
        s[a[i]]++;
    }
    cout<<sum<<endl;
    for(int i=1;i<=1000;i++)if(s[i])printf("%d ",i);
    putchar(10);
}

P1068 [NOIP2009 普及组] 分数线划定

第一眼除了结构体没想到什么好的方法能存$id$号
传送门

#include<bits/stdc++.h>
using namespace std;
struct node{
    int id,pnt;
}a[5050];
bool cmp(node a, node b){
    if(a.pnt!=b.pnt)return a.pnt>b.pnt;
    return a.id<b.id;
}
int n,m,sum;
int main(){
    cin>>n>>m;(m*=3)>>=1;
    for(int i=1;i<=n;i++)cin>>a[i].id>>a[i].pnt;
    sort(a+1,a+1+n,cmp);
    for(int i=1;a[i].pnt>=a[m].pnt&&i<=n;i++)if(a[i].pnt>=a[m].pnt)sum=i;
    printf("%d %d\n",a[m].pnt,sum);
    for(int i=1;a[i].pnt>=a[m].pnt&&i<=n;i++)printf("%d %d\n",a[i].id,a[i].pnt);
}

P1051 [NOIP2005 提高组] 谁拿了最多奖学金

传送门
大结构体 话说$2005$年就已经有结构体了是吗哈哈哈
诶 我代码能力现在还可以 居然一遍过了哈哈 还记得当时第一次做结构体$sort$好几百个错误，把$C?Free$给卡退了 乐了

#include<bits/stdc++.h>
#define N 110
using namespace std;
struct node{
    char nam[30];
    int id,grd,cls,stu,wst,art,money;
}a[N];
bool cmp(node a, node b){
    if(a.money!=b.money)return a.money>b.money;
    return a.id<b.id;
}
int n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i].id=i;
        scanf("%s%d%d",a[i].nam,&a[i].grd,&a[i].cls);
        char ch=getchar();
        while(ch!='Y'&&ch!='N')ch=getchar();
        if(ch=='Y')a[i].stu=1;
        ch=getchar();
        while(ch!='Y'&&ch!='N')ch=getchar();
        if(ch=='Y')a[i].wst=1;
        scanf("%d",&a[i].art);
        if(a[i].grd>80&&a[i].art>=1)a[i].money+=8000,ans+=8000;
        if(a[i].grd>85&&a[i].cls>80)a[i].money+=4000,ans+=4000;
        if(a[i].grd>90)a[i].money+=2000,ans+=2000;
        if(a[i].grd>85&&a[i].wst)a[i].money+=1000,ans+=1000;
        if(a[i].cls>80&&a[i].stu)a[i].money+=850,ans+=850;
    }
    sort(a+1,a+1+n,cmp);
    puts(a[1].nam);
    printf("%d\n%d\n",a[1].money,ans);
}

P1309 [NOIP2011 普及组] 瑞士轮

传送门
本题的思路还和前面的题大体一样，都是结构体排序，但是如果一直无脑$sort$会$TLE，$原因是$sort$会进行过多的浪费操作
注意到赢的选手和输的选手的得分分别是两个有序数组，因此考虑到应用归并排序里的归并思想，将两个有序数组合并成一个有序的大数组
上代码↓

#include<bits/stdc++.h>
#define N 200020
#define reg register
using namespace std;
inline void read(int &x){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
    x=s*w;
}
struct node{
    int pnt,power,id;
}a[N],w[N],l[N];
bool cmp(node a, node b){
    if(a.pnt!=b.pnt)return a.pnt>b.pnt;
    return a.id<b.id;
}
int n,r,q,x,y;
void merge(){
    int p=1,t=1,q=1;
    while(p<=x&&q<=y){
        if(w[p].pnt>l[q].pnt)a[t++]=w[p++];
        else if(w[p].pnt<l[q].pnt)a[t++]=l[q++];
        else{
            if(w[p].id>l[q].id)a[t++]=l[q++];
            else a[t++]=w[p++];
        }
    }
    while(p<=x)a[t++]=w[p++];
    while(q<=y)a[t++]=l[q++];
}
int main(){
    read(n),read(r),read(q);n<<=1;
    for(reg int i=1;i<=n;i++)read(a[i].pnt),a[i].id=i;
    for(reg int i=1;i<=n;i++)read(a[i].power);
    sort(a+1,a+1+n,cmp);
    while(r--){
        for(reg int i=1;i<=n;i+=2){
            if(a[i].power>a[i+1].power)a[i].pnt++,w[++x]=a[i],l[++y]=a[i+1];
            else a[i+1].pnt++,w[++x]=a[i+1],l[++y]=a[i];
        }
        merge();x=y=0;
    }
    cout<<a[q].id<<endl;
}

P1908 逆序对

传送门
上面讲了 用归并排序做
其实还可以用树状数组做 但是现在我已经忘了 等我更到数据结构回来更。

总结

排序算法一直是$OI$界的入门算法，其灵活多变的形式也激发了我们对程序设计竞赛的热爱。
下个专题是二分查找 $xdm$不见不散