vlambda博客
学习文章列表

【C++】运用循环+数组实现排序的四种常用方法(桶排序、冒泡排序、选择排序、插入排序)

分析:

          学习运用循环+数组的方法进行排序不仅仅是为了实现排序功能,更要注意理解其中的算法思想,以便在解决问题时灵活运用。


第一种:桶排序

#include<iostream>using namespace std;int a[100],b[100];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; b[a[i]]++; } for(int i=1;i<=n;i++) if(b[i]>0) cout<<i<<" "; return 0;}


第二种:冒泡排序

#include<iostream>using namespace std;int a[100];int main(){ int n,t; cin>>n; for(int i=1;i<=n;i++) cin>>a[i];//输入数据
for(int j=1;j<=n-1;j++) { for(int k=1;k<=n-j;k++) { if(a[k+1]<a[k]) { t=a[k]; a[k]=a[k+1]; a[k+1]=t; //swap(a[k],a[k+1]); } } }
for(int i=1;i<=n;i++) cout<<a[i]<<' ';//输出排好序后的数据 return 0;}


第三种:选择排序

#include<iostream>using namespace std;int y[100],z[100];//y[100]:原数组,z[100]:最终排好序的数组bool use[100];//标记元素有没有被选择过int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>y[i];//输入原数组
for(int i=1;i<=n;i++)//控制次数 { int p=0; y[p]=101; for(int j=1;j<=n;j++)//遍历数组 { if(use[j]==false&&y[j]<y[p]) p=j; } z[i]=y[p]; use[p]=true; }
for(int i=1;i<=n;i++) cout<<z[i]<<" ";//输出排好序的数组 return 0;}


第四种:插入排序

#include<iostream>using namespace std;int y[100],z[100];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>y[i];//输入原数组
for(int i=1;i<=n;i++)//遍历y[] { bool done=false; for(int j=1;j<=i-1;j++)//遍历z[] { if(y[i]<z[j]) { done=true; for(int k=i;k>j;k--) z[k]=z[k-1];//把z[j]及以后的元素向后移一位 z[j]=y[i]; break; } } if(done==false) z[i]=y[i]; }
for(int i=1;i<=n;i++) cout<<z[i]<<" ";//输出排好序的数组 return 0;}


最后赠送大家一种“无脑”排序

sort()函数排序

#include<iostream>#include<algorithm>//sort()using namespace std;int a[100];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n);//升序  //sort(a+1,a+1+n,greater<int>());//降序  for(int i=1;i<=n;i++) cout<<a[i]<<" "; return 0;}