HM046 冒泡升序

来源： 第 46 集数组-一维数组-冒泡排序

难度： 入门

时间限制： 1s

空间限制： 64MB

题目描述

冒泡排序是最基础的一种排序：比较**相邻**的两个元素，若左边比右边大，就交换它们（交换时同样先用临时变量保住其中一个，不能直接覆盖）。对每一对相邻元素都做完同样的工作后，当前这一轮的最大值会像气泡一样冒到尚未排好的最右边。

一共要做 \(n-1\) 轮（元素个数减 \(1\)）。第一轮要比较 \(n-1\) 对相邻元素，找出最大的那个；第二轮只在剩下的数里找第二大，比较次数再减 \(1\)。第 \(i\) 轮（\(i\) 从 \(0\) 起算）的比较次数是 \(n-i-1\)。直到只剩一个数，不必再比。

外层循环控制轮数，写成 \(i < n-1\)；内层循环控制本轮比较次数，写成 \(j < n-i-1\)。若 arr[j] > arr[j+1]，就交换这两格。整套做完后，数组变成升序。

读入无序整数，用冒泡排序排成升序后输出。

第一行一个整数 \(n\)（\(1 \le n \le 100\)）。

第二行 \(n\) 个整数，绝对值不超过 \(10^9\)。

一行 \(n\) 个整数，表示升序结果，相邻整数之间恰好一个空格，行末换行。

输入 #1

9
4 2 8 0 5 7 1 3 9

输出 #1

0 1 2 3 4 5 7 8 9

输入 #2

3
3 3 1

输出 #2

1 3 3

样例 1 共 \(9\) 个数，要排 \(8\) 轮；第一轮比较 \(8\) 次后，\(9\) 冒到末尾，之后每轮比较次数递减。左边不大于右边时不交换。\(n=1\) 时外层循环不执行，原样输出。相等的数相对次序可以改变，只要最终非递减即可。