8200: 基础排序II：插入排序
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：3
题目描述
此题为插入排序
此题用作练习题，请用插入排序完成此题。
输入
第一行输入一个整数n（0<n<=100000)，表示有n个待排序数据;
随后的n行每行输入一个整数。
随后的n行每行输入一个整数。
输出
升序输出排序结果
样例输入 复制
10
10 9 8 7 6 5 4 3 2 1样例输出 复制
1 2 3 4 5 6 7 8 9 10提示
具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。