【C++】运用循环+数组实现排序的四种常用方法(桶排序、冒泡排序、选择排序、插入排序)
分析:
学习运用循环+数组的方法进行排序不仅仅是为了实现排序功能,更要注意理解其中的算法思想,以便在解决问题时灵活运用。
第一种:桶排序
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;}
第二种:冒泡排序
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;}
第三种:选择排序
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;}
第四种:插入排序
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()函数排序
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;}
