【算法竞赛进阶指南】0x05 排序

2024-03-25 07:04
文章标签 算法 进阶 排序 竞赛 指南 0x05

本文主要是介绍【算法竞赛进阶指南】0x05 排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0x05排序

排序基本算法

785. 快速排序 - AcWing题库姑且用这个评测。

1.选择、插入、冒泡

这类排序是基于比较的排序算法，时间复杂度为O\left ( n^{2} \right )

选择排序

思路比较简单，就是每一次从后面选出最小的数字来与当前这个数字交换

#include<bits/stdc++.h>
const int N=1e6+10;
int n,a[N];
void select_sort()
{for(int i=1;i<=n;i++){int minn=a[i];int sign=i;for(int j=i;j<=n;j++){if(a[j]<minn){minn=a[j];sign=j;}}std::swap(a[i],a[sign]);}
}
signed main()
{std::cin>>n;for(int i=1;i<=n;i++) std::cin>>a[i];select_sort();for(int i=1;i<=n;i++) std::cout<<a[i]<<" ";return 0;
}

插入排序

排序算法——直接插入排序（图文超详细！）-CSDN博客

思路就是每次对当前的数字找到前面第一个大于等于它的j，否则就往后移。

#include<bits/stdc++.h>
const int N=1e6+10;
int n,a[N];
void insert_sort()
{int j;for(int i=2;i<=n;i++){if(a[i]<a[i-1]){int t=a[i];for(j=i-1;j>=1&&t<a[j];j--){//在第一个t>=a[j]的位置退出a[j+1]=a[j];}a[j+1]=t;}}
}
signed main()
{std::cin>>n;for(int i=1;i<=n;i++) std::cin>>a[i];insert_sort();for(int i=1;i<=n;i++) std::cout<<a[i]<<" ";return 0;
}
冒泡排序

冒泡排序-排序-CSDN博客

看里面的动图就很好理解了，从左到右对每两个相邻的数都比较一次，那么到一轮之后最大的数就会跑到最后一个，这样重复n轮就可以实现排序的功能。

#include<bits/stdc++.h>
const int N=1e6+10;
int n,a[N];
void pop_sort()
{for(int i=1;i<=n;i++)//走的次数{for(int j=1;j<=n-i;j++){if(a[j]>a[j+1]){std::swap(a[j],a[j+1]);}}}
}
signed main()
{std::cin>>n;for(int i=1;i<=n;i++) std::cin>>a[i];pop_sort();for(int i=1;i<=n;i++) std::cout<<a[i]<<" ";return 0;
}

2.堆排序、归并排序、快速排序

也是基于比较的排序算法，时间复杂度为O\left ( nlogn \right )

基于比较的排序算法的时间复杂度下界为 O\left ( nlogn \right )，这已经是时间复杂度最优的基于比较的排序算法。

堆排序 

【算法】排序算法之堆排序 - 知乎 (zhihu.com)

归并排序

787. 归并排序 - AcWing题库

先排序再合并

#include<bits/stdc++.h>
const int N=1e6+10;
int a[N],b[N];
void hebin(int l,int r)
{int mid=l+r>>1;int p=l,q=mid+1;for(int i=l;i<=r;i++){if((p<mid+1&&a[p]<=a[q]) || q>r){b[i]=a[p++];}else b[i]=a[q++]; }for(int i=l;i<=r;i++) a[i]=b[i];
}
void merge_sort(int l,int r)
{int mid=l+r>>1;if(l==r) return ;merge_sort(l,mid);merge_sort(mid+1,r);hebin(l,r);	
} 
signed main()
{int n;std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a[i];}merge_sort(1,n);for(int i=1;i<=n;i++)std::cout<<a[i]<<" ";return 0;
}
快速排序

785. 快速排序 - AcWing题库

随便从区间里选择一个点，让左边的数都比他小，右边的数都比它大。

#include<bits/stdc++.h>
const int N=1e6+10;
int n,a[N];
void quick_sort(int l,int r)
{if(l>=r) return ;int x=a[l+r>>1];int i=l-1,j=r+1;while(i<j){do i++;while(a[i]<x);do j--;while(a[j]>x);if(i<j) std::swap(a[i],a[j]);}quick_sort(l,j);quick_sort(j+1,r);}
signed main()
{std::cin>>n;for(int i=1;i<=n;i++) std::cin>>a[i];quick_sort(1,n);for(int i=1;i<=n;i++) std::cout<<a[i]<<" ";return 0;
}

 3.计数排序、基数排序、桶排序

计数排序

【算法】排序算法之计数排序 - 知乎 (zhihu.com)

基数排序

最详细的【基数排序】---排序算法，思路清晰动图保姆级讲解，五分钟搞懂！_csdn基数排序动图-CSDN博客

桶排序

【算法】排序算法之桶排序 - 知乎 (zhihu.com)

排序算法应用

离散化

排序算法的第一个应用是离散化。就是把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。如：问题范围很大但只涉及其中m个数，并且与数值的绝对大小无关，我们就可以把这m个数字与1-m建立映射关系。

void discrete()//离散化
{std::sort(a+1,a+1+n);//去重 for(int i=1;i<=n;i++){if(i==1||a[i]!=a[i-1]){b[++m]=a[i];}}
} 
int query(int x)//查询x的映射 
{return std::lower_bound(b+1,b+m+1,x)-b; 
}

关于lower_bound( )和upper_bound( )的常见用法_lowerbound和upperbound-CSDN博客

简单概括一下就是lower_bound找到第一个<=num的值，upper返回第一个>。这两个函数都是返回一个迭代器，减去初始位置就可以得到下标。

同时在函数参数中加上greater<int>()就把上面的<改成了>。

103. 电影 - AcWing题库

e这题就是给定n个编号，从m个里面发现人数最大的解就可以。其实只需要开个map记录每种语言有多少人会就行了，毕竟没人关心谁会谁不会。循环里维护sign即可。

#include<bits/stdc++.h>
using ll=long long;
//#define int ll
const int N=2e5+10;
int n,m,k;
int a,b[N],c[N];
std::map<int,int> mp;//记录懂这个语言的人的个数 void solve()
{std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a;	mp[a]++;//std::cout<<a<<" "<<mp[a]<<'\n';}	std::cin>>m;int maxn=0,sign=m,maxnn=0;for(int i=1;i<=m;i++){std::cin>>b[i];}for(int i=1;i<=m;i++){std::cin>>c[i];int now=mp[b[i]];if(now>maxn){//std::cout<<i<<'\n';maxn=now,sign=i;maxnn=mp[c[i]];}else if(now==maxn){if(mp[c[i]]>maxnn){maxnn=mp[c[i]];sign=i;}}	}std::cout<<sign<<'\n';
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

中位数

104. 货仓选址 - AcWing题库

需要某家店到所有店的距离之和最短，奇数时最中间那个点最短，偶数时中间两个点都行。

#include<bits/stdc++.h>
using ll=long long;
//#define int ll
const int N=2e5+10;
int n,m,k;
int a[N];
ll ans;
void solve()
{std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a[i];	}	std::sort(a+1,1+a+n);for(int i=1;i<=n;i++){ans+=std::abs(a[i]-a[n/2+1]);} std::cout<<ans;
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}
105. 七夕祭 - AcWing题库

专门开了个博客写这个问题，会详细点。 

【算法】环形纸牌均分问题-CSDN博客

#include<bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
const int mod=1e9+7;
int row[N],col[N],sr[N],sl[N];
int n,m,s;
ll cnt1=-1,cnt2=-1;
void solve()
{std::cin>>n>>m>>s;for(int i=1;i<=s;i++){int x,y;std::cin>>x>>y;row[x]++,col[y]++;}if(s%n==0)//对行 {cnt1=0;int t=s/n;for(int i=1;i<=n;i++){row[i]-=t;sr[i]=sr[i-1]+row[i];	}  std::sort(sr+1,sr+1+n);int mid=1+n/2;for(int i=1;i<=n;i++){cnt1+=std::abs(sr[i]-sr[mid]);}}if(s%m==0)//对列{cnt2=0;int t=s/m;for(int i=1;i<=m;i++){col[i]-=t;sl[i]=sl[i-1]+col[i];	}  std::sort(sl+1,sl+1+m);int mid=1+m/2;for(int i=1;i<=m;i++){cnt2+=std::abs(sl[i]-sl[mid]);}}if(cnt1==-1&&cnt2==-1){std::cout<<"impossible"<<'\n';}else{if(cnt1!=-1&&cnt2!=-1){std::cout<<"both"<<' ';std::cout<<cnt1+cnt2<<'\n';}else if(cnt1!=-1){std::cout<<"row"<<' ';std::cout<<cnt1<<'\n';}else{std::cout<<"column"<<' ';std::cout<<cnt2<<'\n';}}
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}
106. 动态中位数 - AcWing题库

依次读入一个整数序列，每当已经读入的个数为奇数时，输出已读入的序列的中位数。

对数组排序的时间复杂度是nlogn，但是求解中位数实际上并不要求这个数组有序。我们只需要找到一个数字，左边一半都比他小，右边一半都比他大。

如何让左边一半都比它小，右边一半都比他大呢？我们可以建两个堆，左边一个大根堆，右边一个小根堆。是不是只要大根堆所有元素都比小根堆的所有元素小，并且数量满足一定关系就好了？

我们假定中位数，n/2+1是大根堆的堆顶，那么左边有n/2+1个元素，右边有n/2个元素。那么需要满足的数量关系是不是就是，leftsize-1==rightsize。

因此，进来一个数我们就把他放进大根堆。如果，大根堆的top比小根堆的top还大了，我们只需要交换两个top即可，这样我们就维护了左边的始终小于右边的。

在堆稳定之后，我们就要判断左边堆的数量是不是太多了。如果是就弹出top并放入right即可。

#include<bits/stdc++.h>
using ll=long long;
const int N=1e4+10;
int a[N];
void solve()
{int sno,n;std::cin>>sno>>n;std::cout<<sno<<" "<<n/2+1<<'\n';std::priority_queue<int> left;//大根堆std::priority_queue<int,std::vector<int>,std::greater<int>> right;int cnt=0;for(int i=1;i<=n;i++){int x;std::cin>>x;left.push(x);if(!right.empty()&&left.top()>right.top()){int a=left.top(),b=right.top();left.pop(),right.pop();right.push(a),left.push(b);}//左边n/2+1，右边n/2if(left.size()-1>right.size())//左边太多了{right.push(left.top());left.pop();}if(i%2){cnt++;std::cout<<left.top()<<" ";if(cnt%10==0) std::cout<<'\n';//达到十个就回车}}if(cnt%10) std::cout<<'\n';
}
signed main()
{int t=1;std::cin>>t;while(t--){solve();}return 0;
}

第k大数

786. 第k个数 - AcWing题库

这个也可以用上面的对顶堆来做，只需要把大小条件改了就行。每次进堆之前比较，如果当前数比lefttop大就丢到右边，否则把lefttop抛出，把这个数塞进去。

#include<bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
int x;
int n,k;
void solve()
{std::priority_queue<int> left;std::priority_queue<int,std::vector<int>,std::greater<int>> right;std::cin>>n>>k;for(int i=1;i<=n;i++){std::cin>>x;left.push(x);	if(left.size()>k){right.push(left.top());left.pop();}if(!right.empty()&&left.top()>right.top()){int a=left.top(),b=right.top();left.pop(),right.pop();left.push(b),right.push(a);}}std::cout<<left.top();
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

还有一种做法是快速排序，快速排序的过程是每次选择一个数让左边都比他小，右边都比他大，然后再分别递归两边进行排序。然而，我们追求的不是有序的数组，我们只需要知道第k大的是什么就好，因此我们每次可以舍弃一半的区间。平均情况下时间复杂度为O(n)。

#include<bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
int a[N];
int n,k;
int quick_sort(int l,int r)
{if(l==r) return a[l];int mid=l+r>>1;int x=a[mid];int i=l-1,j=r+1;while(i<j){do i++;while(a[i]<x);do j--;while(a[j]>x);if(i<j) std::swap(a[i],a[j]);}if(j>=k) return quick_sort(l,j);else return quick_sort(j+1,r);
}
void solve()
{std::cin>>n>>k;for(int i=1;i<=n;i++){std::cin>>a[i];}std::cout<<quick_sort(1,n);
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

比较一下时间，还是快排优化之后的代码更加理想。

对于对顶堆这个做法主要是可以在线以O1的时间处理，如果离线处理还不如直接排序。

逆序对

对一个序列a，如果i<j 并且 a[i] >a[j]，则称a[i] 与a[j]构成逆序对。

求逆序对的常用方法是归并排序，还有树状数组（后面应该会学）。

贴个归并排序。

#include<bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
int a[N],b[N];
int n,k;
void hebin(int l,int r)
{int mid=l+r>>1;int i=l,j=mid+1;int k=0;while(i<=mid&&j<=r){if(a[i]<=a[j]) b[++k]=a[i++];else b[++k]=a[j++];	}	while(i<=mid) b[++k]=a[i++];while(j<=r) b[++k]=a[j++];for(int i=l,j=1;i<=r,j<=k;i++,j++) a[i]=b[j];
}
void merge_sort(int l,int r)
{if(l==r) return ;int mid=l+r>>1;merge_sort(l,mid);merge_sort(mid+1,r);hebin(l,r);
}
void solve()
{std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a[i];}merge_sort(1,n);for(int i=1;i<=n;i++){std::cout<<a[i]<<" ";}
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

 如果要计算逆序对个数只需要加上一段代码（逆序对个数记得开long long！

为啥是这样呢？

再合并数组里，我们合并l~mid和mid~r这两段区间，此时指针走到了i，则i~mid都会比j小，因此加上这段区间的长度mid-i+1即可。

107. 超快速排序 - AcWing题库

 确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序

把每一对逆序的交换就行了呗，实际上就是求逆序对的个数。

#include<bits/stdc++.h>
using ll=long long;
const int N=5e5+10;
int a[N],b[N];
int n,k;
ll cnt;
void hebin(int l,int r)
{int mid=l+r>>1;int i=l,j=mid+1;int k=0;while(i<=mid&&j<=r){if(a[i]<=a[j]) b[++k]=a[i++];else b[++k]=a[j++],cnt+=mid-i+1;	}	while(i<=mid) b[++k]=a[i++];while(j<=r) b[++k]=a[j++];for(int i=l,j=1;i<=r,j<=k;i++,j++) a[i]=b[j];
}
void merge_sort(int l,int r)
{if(l==r) return ;int mid=l+r>>1;merge_sort(l,mid);merge_sort(mid+1,r);hebin(l,r);
}
void solve()
{std::cin>>n;if(n==0) return ;cnt=0;for(int i=1;i<=n;i++){std::cin>>a[i];}merge_sort(1,n);std::cout<<cnt<<'\n';
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t=1;//std::cin>>t;while(t){solve();if(n==0) break;}return 0;
}
108. 奇数码问题 - AcWing题库

可以把棋盘抽象出来，左右交换不会改变元素的排列。因此我们只考虑上下交换，当m为奇数的时候，上下交换会_23 456 789->423 _56 789绕过2个数，这必定是偶数，也就是每次交换只改变偶数次逆序对。如果给定的两个状态的逆序对个数的奇偶性不同，那么怎么都不会成功。因此这题我们只需要判断两种状态的逆序对个数奇偶性即可。

如果n是偶数呢？每次交换绕过奇数个，但我们只会换空格行的差次。为什么？虽然我们可以来回不停的换，但来回换并不会一下逆序对的奇偶性。因此判断逆序对数之差和行数之差奇偶性是否相同即可。

参考：排序与贪心知识点小结 - a1b3c7d9 - 博客园 (cnblogs.com)

因为这题难点在于思维不在于代码，所以这里偷个懒直接cp别人代码hh。

#include <bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,a[N*N],b[N*N],c[N*N],i,j,k;
long long cnt;
void merge(int a[],int l,int r)
{if (r-l<1)return ;int mid=(l+r)>>1;merge(a,l,mid);merge(a,mid+1,r);int i=l,j=mid+1;for (int k=l; k<=r; k++){if (j>r || i<=mid && a[i]<=a[j])b[k]=a[i++];else{cnt+=mid-i+1;b[k]=a[j++];}}for (int k=l; k<=r; k++)a[k]=b[k];
}
signed main()
{ios::sync_with_stdio(false);while(cin>>n){int ok=0,x;for (i=1; i<=n*n; i++){cin>>x;if (x==0)ok=1;elsea[i-ok]=x;}ok=0;for (i=1; i<=n*n; i++){cin>>x;if (x==0)ok=1;elsec[i-ok]=x;}cnt=0;memset(b,0,sizeof(b));merge(a,1,n*n);long long ans=cnt;memset(b,0,sizeof(b));cnt=0;merge(c,1,n*n);if ((ans&1)==(cnt&1))puts("TAK");elseputs("NIE");}return 0;
}

 

这篇关于【算法竞赛进阶指南】0x05 排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/844200。

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
Retrieval-based-Voice-Conversion-WebUI模型构建指南

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI（简称 RVC）模型是一个基于 VITS（Variational Inference with adversarial learning for end-to-end Text-to-Speech）的简单易用的语音转换框架。 具有以下特点 简单易用：RVC 模型通过简单易用的网页界面，使得用户无需深入了
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2