题目描述

输入 N 个整数，使用插入排序法从小到大输出。

输入格式

第一行 1 个正整数： N ，范围在 [1,1000]。

第二行 N 个整数，每个整数范围在 [0,1000000]。

输出格式

一行 N 个从小到大的整数。

样例

4
5 3 6 1

1 3 5 6

4
5 5 1 9

1 5 5 9

完成程序

#include<bits/stdc++.h>
using namespace std;
int n,a[1001];
int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	 
	for(int i=1;填空(1);i++)
		for(int j=填空(2);填空(3);j++)
			if(填空(4)) swap(a[i],a[j]);
	
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

上面的程序，每一轮(i 循环) 都是不断的做前项和后项的比较，如果后项更小，就交换两者。因此有可能在一轮 i 循环中执行了很多次前后交换。所以，可以做出改良改良。每一轮先确定最小的数字是什么，以及它的位置，最后只 swap 一次。

#include<bits/stdc++.h>
using namespace std;
int n,a[1001];
int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	 
	int mina,p; 
	for(int i=1;填空(5);i++)
	{
		p = i;
		mina = a[i];
		for(int j=填空(6);填空(7);j++)
		{
			if(填空(8))
			{
				填空(9);
				mina = a[j];
			}
		}
		
		if(填空(10)) swap(a[i],a[p]);		
	}

	
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);

	return 0;
}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}

填空(9):{{ input(9) }}

填空(10):{{ input(10) }}

补充说明

1. 选择排序的核心思想就是每一轮选出最小的放在对应的位置。（第一小的放在第一个位置，第二小的放在第二个位置......）。上面两种写法都符合选择排序的原理，后者更佳，因为可以减少 swap 的次数。

2. 第二种写法的的理解要点是：j 变量的循环是找出该轮中的最小值，最小值存入 mina 变量，最小值的出现位置记录在 p 变量。

3. 选择排序的一种很重要的特点是不稳定。稳定性指的是，如果有两个元素，其排序的关键特性一致，排序完之后的前后顺序和排序之前的前后顺序是否保持一致。如果保证保持一致，就是稳定，反之，则是不稳定。冒泡排序、插入排序 都是稳定的，但是选择排序是不稳定的。下面举例说明：

有 3 个数 5,5,3，按照上面的代码进行选择排序（在这个例子中，上面的两种代码的情况会一样）。因为有 2 个 5，我们故意加以区分，用不同颜色标注。我们关注排序完之后，两个 5 的位置有没有发生前后变化即可理解选择排序的稳定性。

在第一轮循环中，第 1 个 5 比后面的 3 大，所以，就交换了。3 去了最前面，橙色的 5 去了最后面。

在第二轮循环中，没有发生位置交换。然后排序就结束了。

可以看到，排序前橙色的 5 在前面，排序后橙色的 5 在后面。可见，插入排序是不稳定的排序。