选择排序算法简介

选择排序（ Selection sort）是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序算法通过选择和交换来实现排序，其排序流程如下：

（1）首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。

（2）接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换

（3）然后，这样不断重复，直到最后两个数据完成交换。最后，便完成了对原始数组的从小到大的排序。

时间复杂度为 $O(n^2)$，空间复杂度为$O(1)$，不稳定排序。


题目描述

给定n个整数的序列，用选择排序法对其重小到大排序输出。

输入

第一行一个整数 n (n<=1000)， 第二行n个整数 (0~$10^9$）。

输出

一行从小到大排好序的数字，每个数之间以空格隔开。

样例

样例输入：

9
8 6 7 2 3 9 5 4 1

输出：

1 2 3 4 5 6 7 8 9