冒泡排序算法简介

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。 时间复杂度为 O(n2)，空间复杂度为，稳定排序。 【冒泡排序过程】

1. 第一轮 在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，就交换这两个数字的位置。

由于6 ＜ 7，所以交换这两个数字。

完成后，天平往左移动一个位置，比较两个数字的大小。此处4 ＜ 6，所以无须交换。

继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。

不断对数字进行交换，天平最终到达了最左边。通过这一系列操作，序列中最小的数字就会移动到最左边。

最左边的数字已经归位。 2. 第二轮 将天平移回最右边，然后重复之前的操作，直到天平到达左边第2 个位置为止。

当天平到达左边第2 个位置时，序列中第2 小的数字也就到达了指定位置。

3. 第三轮 将天平再次移回最右边，重复同样的操作直到所有数字都归位为止。

排序中……

排序中……

排序完成。

冒泡排序动画演示（可以点击刷新重复查看）

【总结】 在冒泡排序中，第 1 轮需要比较 n−1 次，第 2 轮需要比较 n−2 次，⋯，第 n−1 轮需要比较 1 次。因此，总的比较次数为 (n−1)+(n−2)+…+1≈$n^2/2$。这个比较次数恒定为该数值，和输入数据的排列顺序无关。因此，冒泡排序的时间复杂度为 $O(n^2)$。

题目描述

给定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