4大排序的题解

冒泡排序

#include <bits/stdc++.h>
using namespace std;
int n,a[114514];
void Bubble_sort()
{
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=n-i;j++)
			if(a[j]>a[j+1]) swap(a[j],a[j+1]);
 } 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	Bubble_sort();
	for(int i=1;i<n;i++)
		cout<<a[i]<<" ";
	cout<<a[n]<<endl;
}

---

选择排序

#include <bits/stdc++.h>
using namespace std;
int n,a[114514];
void selet_sort()
{
	for(int i=1;i<=n;i++)
	{
		int idx=0;
		for(int j=i;j<=n;j++)
			if(a[j]<a[idx]) idx=j;
		swap(a[i],a[idx]);
	}
}
int main()
{
	cin>>n;
	a[0]=99999;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	selet_sort();
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
}

---

插入排序

#include <bits/stdc++.h>
using namespace std;
int n,a[114514];
void insert_sort()
{
	for(int i=2;i<=n;i++)
	{
		int t=a[i],idx=i;
		for(int j=i-1;j>=1;--j)
		{
			if(t<a[j])
			{
				a[j+1]=a[j];
				idx=j;
			}
		}
		a[idx]=t;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	insert_sort();
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
}