题目描述

输入 $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 x[1001];
int main(){
	int n;
	scanf("%d",&n);

	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);

	for(int i=__填空(1)__;i<=n;i++){
		int base = x[i];
		int j = __填空(2)__;

		while(j>=1 && __填空(3)__ ){
			__填空(4)__;
			j--;
		}
		__填空(5)__ = base;
	}

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

	return 0;
}

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

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

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

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

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

补充说明

题目说了是插入排序，这是一个专有名词，这是一个大家都公认的算法。你必须按照这个公认的算法来完成这个程序。就好比语文考试，老师让你写记叙文，结果本来想写你你爸爸，讲述他的外貌，说你爸爸在哪里工作，他有什么性格特点，他平常如何如何关心你学习....那整篇作文文体都变了，这篇作文就是不及格的。

回到正题，插入排序就是插入排序，大家如果有点忘记了，请找回之前的课件来看。这里简单说明一下这个算法的特点：

1. 这个算法会把数据分成 2 部分，一部分是有序的，一部分是无序的。整个过程，就是把无序的数据一个个插入到有序的数字里面去。这个过程类似我们打扑克牌的时候的整理过程。在上面的程序里，下标 1 到 i-1 是有序的，下标 i 到 n 是无序的。最开始，第一个数字 $a_i$ 可以认为是有序的（就 1 个数字，当然有序啊）。

2. 第一层循环，可以理解成把 $a_i$ 插入到前面 1 到 i-1 范围内的某个位置。这个位置怎么确定，就是插入排序的关键点。因为这条题是从小到大排序，我们插入的位置应该是 $a_k \le a_i$ ，满足这个条件的时候 ，$a_i$ 应该放在 $a_k$ 的后面，也就是说插入到 k+1 这个位置。

3. 找插入位置的时候，$j$ 一定要从后往前前找，这是一个关键点。这样做有好处，假如有序数列的最后一个（$a_{i-1}$）小于等于 $a_i$ ，那比较一次就足够了，就退出了循环了。所以，如果数据本身有序，插入排序是很快的，就是做了 $n-1$ 次比较。如果 $j$ 的循环从前往后看，就没有了这个特点了，那就不是插入排序算法了。

4. 把 $a_i$ 插入到 j+1 的这个位置，意味着 $a_1$ 到 $a_j$ 不用动，$a_{j+1}$ 到 $a_{i-1}$ 全部往后挪一个位置，最后，把 $a_i$ 赋值给 $a_{j+1}$