0.对比
算法名称 | 时间复杂度 | 稳定性 |
---|---|---|
1计数排序 | (O(N)) | √ |
2选择排序 | (O(N^2)) | × |
3冒泡排序 | 最坏(O(N^2)),最好(O(N)) | √ |
4插入排序 | 平均(O(N^2)),最好(O(N)) | √ |
5基数排序 | (O(lencdot N)) | √ |
6归并排序 | (O(NlogN)) | √ |
7快速排序 | 平均(O(NlogN)),最坏(O(N^2)) | × |
8希尔排序 | 争议,平均(O(NlogN)),下限(O(N^{1.5})) | × |
9堆排序 | (O(NlogN)) | × |
一、计数排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;//元素最大值
int a[maxn+5];
int main(){
int n;scanf("%d",&n);
for(int i=1,x;i<=n;i++)scanf("%d",&x),a[x]++;
for(int i=1;i<=maxn;i++)for(int j=1;j<=a[i];j++)printf("%d ",i);
return 0;
}
算法描述:全部扔进桶里,最后一个个倒出来。
其他:具有局限性,数组大小为元素上限。
复杂度最低的排序算法(O(n+m))(n为元素数,m为元素大小上界),稳定。
二、选择排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;//元素个数
int a[maxn+5];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
int k=i;
for(int j=i+1;j<=n;j++)if(a[j]<a[k])k=j;
if(k!=i)swap(a[i],a[k]);
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
算法描述:每次找个最小的放前面来。
(O(n^2)),不稳定。
三、冒泡排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a[maxn+5];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++){
int f=0;
for(int j=1;j<=n-i;j++){
if(a[j]>a[j+1])swap(a[j],a[j+1]),f=1;
}
if(!f)break;
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
算法描述:每次比较相邻元素。优先级高的元素(大气泡)逐渐上升。
其他:冒泡排序交换的次数为逆序对数。
最坏(O(n^2)),最好时(O(n))。
稳定排序。
四、插入排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a[maxn+5];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
int x=a[i],j=i-1;
for(;j>0&&x<a[j];j--)a[j+1]=a[j];
a[j+1]=x;
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
算法排序:维护前缀有序,把当前元素插前面去。
平均为(O(n^2)),最好(O(n))。
稳定。
五、基数排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int s[10][maxn+5],a[maxn+5];
int main(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
int len[10],d=1;
for(int i=0;i<10;i++){
memset(len,0,sizeof(len));
for(int j=0;j<n;j++){
int k=a[j]/d%10;//求第i位上的数值
s[k][len[k]++]=a[j];
}
int m=0;
for(int j=0;j<10;j++)for(int k=0;k<len[j];k++){
a[m++]=s[j][k];
}
d*=10;
}
for(int i=0;i<n;i++)printf("%d ",a[i]);
}
算法描述:从最低位开始,依次进行一次排序。
其他:排序的前提是所有元素都非负。如果存在负数,可以通过都加上一个很大的值来转化为非负数元素序列。
(O(ncdot m)),(m为最长数位长度)。
稳定。
六、归并排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a[maxn+5],b[maxn+5],cnt=0;
void merge(int l,int r){
if(l==r)return;
int mid=l+r>>1;
merge(l,mid);merge(mid+1,r);
int i=l,j=mid+1,k=l;
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 o=l;o<=r;o++)a[o]=b[o];
}
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
merge(1,n);
printf("%d
",cnt);
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
算法描述:分治,将两个有序序列合并。
其他:可在(O(NlogN))时间内得到逆序对数。
(O(nlogn))。归并两个长度均为n的有序数组时,最多比较次数为(2n-1)(NOIP2017初赛)。
稳定。
七、快速排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a[maxn+5],n;
void Qsort(int l,int r){
if(l>=r)return;
int i=l,j=r,mid=a[(l+r)>>1];
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j)swap(a[i++],a[j--]);
}
Qsort(l,j),Qsort(i,r);
}
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
Qsort(1,n);
for(int i=1;i<=n;i++)printf("%d%c",a[i],i==n?'
':' ');
}
算法描述:选一个基量,将大于他的元素放后面,小于他的元素放前面,再递归两个子区间。
其他:冒泡排序的改进。
平均时间复杂度为(O(nlogn)),最坏情况下(O(n^2))。
不稳定。
八、希尔排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a[maxn+5];
int main(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int step=n/2;step>=1;step/=2){//下标增量
for(int i=step;i<n;i++)if(a[i]<a[i-step]){
int k=i-step,tmp=a[i];
while(k>=0&&tmp<a[k]){
a[k+step]=a[k];
k-=step;
}
a[k+step]=tmp;
}
}
for(int i=0;i<n;i++)printf("%d%c",a[i],i==n?'
':' ');
}
算法描述:按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,完成排序。
其他:插入排序的改进版。
复杂度存在争议,下限是(O(nlogn)),平均(O(n^{1.5}))。
不稳定。
九、堆排序
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
struct Heap{
int a[maxn+5],sz;
void init(int n){
sz=n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
}
/*void up(int x){
while(x>1){
int fa=x/2;
if(a[x]<a[fa])swap(a[x],a[fa]);
else return;
x=fa;
}
}*/
void down(int x){//维护小根堆
while(2*x<=sz){
int son=x<<1;
if(son+1<=sz&&a[son]>a[son+1])son|=1;//找较小的儿子
if(a[x]>a[son])swap(a[x],a[son]);
else return;
x=son;
}
}
}heap;
int main(){
int n;scanf("%d",&n);
heap.init(n);
for(int i=n/2;i>=1;i--)heap.down(i);//对于非叶子节点
for(int i=1;i<=n;i++){
printf("%d ",heap.a[1]);
heap.a[1]=heap.a[heap.sz--];
heap.down(1);
}
}
算法描述:利用数据结构堆。
每次向上、向下操作都是logn,时间复杂度为(O(nlogn))。
不稳定。
补充博客
Upd
再补充一下快速排序的其他板子
快速排序板子#2
inline void Qsort(int l,int r){
if(l>=r)return;
register int i=l,j=r,key=a[l];
while(i<j){
while(i<j&&a[j]>=key)j--;
if(i<j)a[i]=a[j];
while(i<j&&a[i]<=key)i++;
if(i<j)a[j]=a[i];
}
a[i]=key;
Qsort(l,i-1),Qsort(i+1,r);
}
快速排序板子#3
inline void Qsort(int l,int r){
if(l>=r)return;
register int i=l,j=r,key=a[l];
while(i<j){
while(i<j&&a[j]>=key)j--;
swap(a[i],a[j]);
while(i<j&&a[i]<=key)i++;
swap(a[i],a[j]);
}
Qsort(l,i-1),Qsort(i+1,r);
}
以及基于快速排序的(O(N))查找序列第K大(小)值
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int N=1e7+10;
int n,a[N];
int Qsort(int l,int r,int k){
int key=a[l];
int i=l,j=r;
while(i<j){
while(i<j&&a[j]>=key)j--;
if(i<j)a[i]=a[j];
while(i<j&&a[i]<=key)i++;
if(i<j)a[j]=a[i];
}
a[i]=key;
int numl=i-l+1;
if(numl==k)return key;
else if(k<numl)return Qsort(l,i-1,k);
return Qsort(i+1,r,k-numl);
}
int main(){
// freopen("findkth.in","r",stdin);
// freopen("findkth.out","w",stdout);
int k;scanf("%d%d%d",&n,&a[1],&k);
for(int i=2;i<=n;i++)a[i]=1ll*a[i-1]*a[i-1]%mod;
printf("%d",Qsort(1,n,n-k+1));
}