P12074

插入排序2

难度 小学 算法入门 插入排序
讨论 统计 233通过 421提交 55.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定一个包含 N 个整数的数组,请使用直接插入排序算法将其按从小到大的顺序排序,并输出排序后的结果。

直接插入排序的基本思想:

  • 将数组分为已排序区和未排序区,初始时已排序区只包含第一个元素。
  • 每次从未排序区取出第一个元素,将其插入到已排序区的正确位置(保持有序),直到所有元素都进入已排序区。

输入

  • 第一行包含一个整数 N ( 1 \le N \le 100000 ),表示数组元素的个数。
  • 第二行包含 N 个整数,表示待排序的数组元素,每个整数之间用空格隔开。

输出

输出一行,包含 N 个整数,按从小到大顺序排列,每个整数之间用一个空格隔开。

样例

样例 1
输入
10
7 2 5 4 9 6 3 10 1 8
输出
1 2 3 4 5 6 7 8 9 10
样例 2
输入
15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
样例 3
输入
6
998 547812 31546 1245 1 3
输出
1 3 998 1245 31546 547812

提示

数据范围与约定

  • 1 \le N \le 100000
  • 待排序的整数绝对值不超过 10^9
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交