排序
2022/9/3 23:23:35
本文主要是介绍排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
其实排序能用的上的就三个:快排,归并,基排(\(O(wys)\))。(其实priority_queue可能也算)
快排很好说,sort就行。还有一个stable_sort是相同大小元素顺序不变的稳定排序算法。(事实上我随了1e7个随机数,sort是3.412s,stable_sort是3.569s)
然后是归并。这个可以用来求逆序对,而且理解它的原理也很重要(今天A层考试又考了个这个然后我不会,就是这个题)。
首先说一下归并的原理。oi-wiki的递归部分有一句话可以大致说明:
如何给一堆数字排序?答:分成两半,先排左半边再排右半边,最后合并就行了,至于怎么排左边和右边,请重新阅读这句话。
这就是归并排序。我们分治地排序左半边和右半边,然后再把它们合并。显然关键的地方是合并。我们可以顺序扫描左半边和右半边两个数组,哪个比较小就放到排序后的数组里。这个东西根据主定理复杂度是\(O(n\log n)\)的。
直接说有点不明显,写点注释。
int a[1000010],b[1000010]; void mergesort(int l,int r){ if(l==r)return; int mid=(l+r)>>1; mergesort(l,mid);mergesort(mid+1,r);//向下递归 int i=l,j=mid+1,k=l;//i为左区间指针 j为右区间指针 k为整体的指针(也就是排了多少个元素) while(i<=mid&&j<=r){ if(a[i]<=a[j]){ b[k]=a[i];i++;k++;//移动到辅助数组里 为保证稳定需要前半段在前面 也就是<= } else{ b[k]=a[j];j++;k++; } } while(i<=mid){ b[k]=a[i];i++;k++;//如果还有没有转移完的数则转移 } while(j<=r){ b[k]=a[j];j++;k++; } for(int i=l;i<=r;i++)a[i]=b[i];//复制回原数组 }
然后归并排序使得其支持一个操作:求逆序对数。
逆序对:对于数列\(a\),使\(i<j,a_i>a_j\)的数对为逆序对(就是前面的数比后面的数大)。先上代码再解释。
void mergesort(int l,int r){ if(l==r)return; int mid=(l+r)>>1; mergesort(l,mid);mergesort(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 i=l;i<=r;i++)a[i]=b[i]; }
对就加了一句。原理是什么?
观察我们每次统计答案的时间,是在\(a_j>a_i\)的时候。换言之,由于我们之前左右的数组已经排好序了,所以\(a_j\)一定大于在此之前的所有\(a_i\),而小于之后的所有\(a_i\)。所以我们只需要统计\(a_j\)对所有\(a_i\)的贡献就行了,也就是我们加上的数字。
- 基数排序
基数排序是一种稳定的、非比较性的排序算法。假设我们有一堆数,我们可以稳定地从低位到高位排序,这样最后的结果就是排好序的结果。但是十进制排序一堆取模相当慢,所以开二进制。基数的选取大概有两种:\(2^8\)排序四次和\(2^{16}\)排序两次。
洛谷的题解一大堆玩指针的看不懂,所以写了个非指针式的自用。
int n,r1[256],r2[256],r3[256],r4[256]; int a[100010],b[100010]; void mysort(int a[],int b[]){ for(int j=1;j<=n;j++){ r1[a[j]&255]++; r2[(a[j]>>8)&255]++; r3[(a[j]>>16)&255]++; r4[a[j]>>24]++;//把每一位按基数扒出来扔到桶里 } for(int i=1;i<=255;i++){ r1[i]+=r1[i-1]; r2[i]+=r2[i-1]; r3[i]+=r3[i-1]; r4[i]+=r4[i-1]; }//记录前缀和 for(int j=n;j>=1;j--){ b[r1[a[j]&255]--]=a[j]; } for(int j=n;j>=1;j--){ a[r2[(b[j]>>8)&255]--]=b[j]; } for(int j=n;j>=1;j--){ b[r3[(a[j]>>16)&255]--]=a[j]; } for(int j=n;j>=1;j--){ a[r4[b[j]>>24]--]=b[j]; }//进行四次桶排序 }
如果理解了可以换成指针,卡常的话请务必使用指针(虽然容易re爆零)(洛谷板子指针和非指针能差出20ms)
void mysort(int a[],int b[]){ int *i,tmp; for(i=a+1;i!=a+n+1;i++){ tmp=*(int *)i; r1[tmp&255]++; r2[(tmp>>8)&255]++; r3[(tmp>>16)&255]++; r4[tmp>>24]++; } for(int j=1;j<=255;j++){ r1[j]+=r1[j-1]; r2[j]+=r2[j-1]; r3[j]+=r3[j-1]; r4[j]+=r4[j-1]; } for(i=a+n;i!=a;i--){ tmp=*i; b[r1[tmp&255]--]=*i; } for(i=b+n;i!=b;i--){ tmp=*i; a[r2[(tmp>>8)&255]--]=*i; } for(i=a+n;i!=a;i--){ tmp=*i; b[r3[(tmp>>16)&255]--]=*i; } for(i=b+n;i!=b;i--){ tmp=*i; a[r4[tmp>>24]--]=*i; } }
这篇关于排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-0601-电商商品中心解密:仅凭SKU真的足够吗?
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能