12074 - 插入排序2

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

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

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

输入

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

输出

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

样例

输入

10
7 2 5 4 9 6 3 10 1 8

输出

1 2 3 4 5 6 7 8 9 10

输入

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

输入

6
998 547812 31546 1245 1 3

输出

1 3 998 1245 31546 547812

提示

数据范围与约定

  • 1 \le N \le 100000
  • 待排序的整数绝对值不超过 10^9
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题