【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;
}