[数据结构与算法]例2：数列排序

题目描述

输入n(n<=1000)个数字a[i] (a[i] <1e9)，将其从小到大排序后输出。

我们根据这道题介绍三种简单排序算法，由于这几种算法时间复杂度都是O(n^2),所以了解即可。

解法一：选择排序

选择排序就是模拟将最小值依次放到指定位置的过程，即每一轮将未放置到指定位置的最小数放到最左边，代码如下：
?

#include<iostream>
using namespace std;
const int N=1e5;
int a[N]; 
int n,m,tmp;
int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j])
			{
				swap(a[i],a[j]);
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<' ';
	}
		
	return 0;
}

解法二： 冒泡排序

与选择排序不同，冒泡排序是将最大的一项放到最右边，由于在每一轮中最大的数都会像冒泡一样从左边移到右边，所以叫冒泡排序。代码如下：

#include<iostream>
using namespace std;
const int N=1e5;
int a[N]; 
int n,m,tmp;
int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<' ';
	}
		
	return 0;
}

解法三：插入排序

插入排序可以理解为打扑克时整牌的过程，我们在打扑克抓到牌时，一般会看看已经整理好的手牌，然后插入到合适的位置。

我们在每次抓到牌时都会整理，将整理过的牌称为有序区，每次抓到牌后从有序区末尾开始比较，如果待插牌比正在比较的牌小，就把正在比较的牌向后放一格（为待插牌空出位置），然后继续向前比较，直到遇到不大于自己的牌或成为第一个为止，这时待插牌就可以插入空出的位置了。

代码如下：
?

#include<iostream>
using namespace std;
const int N=1e5;
int a[N]; 
int n,m,tmp;
int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	for(int i=1;i<n;i++)
	{
		int now=a[i];
		for(int j=i-1;j>=0;j--)
		{
			if(a[j]>now)
			{
				a[j+1]=a[j]; // j向右移动 
			}
			else break;
			a[j]=now; // 插入空位 
		}		
	}
	
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<' ';
	}
		
	return 0;
}