故事引入
老师让同学们把数字卡片按从小到大排好。小竞用了“选择排序”的方法:
每一轮,她先找出剩下的卡片中最小的那张,然后把它放到最前面。
这样,经过若干轮,所有的卡片就都有序了。
现在请你帮助小竞实现这个方法,并且把每一轮“选中的最小数字和谁交换”的过程记录下来。
题目描述
输入 n 个整数,使用选择排序将它们按从小到大(升序)排序。
要求:
- 每一轮(从第1轮到第n-1轮)都要输出本轮找出的最小值以及与哪个位置的元素交换。
- 如果最小值已经在正确的位置(即不需要交换),则输出“本轮无需交换”。
- 最后输出排序后的完整数组。
输入格式
第一行一个整数 n(1 ≤ n ≤ 1000)。
第二行 n 个整数,用空格隔开。
输出格式
- 第一行输出初始数组:
Initial:后跟数组元素,空格隔开。 - 接下来
n-1行,每行表示一轮的结果:
Round i: 找到最小值 X,与位置 pos 交换(如果交换了)
或者Round i: 找到最小值 X,已在正确位置,无需交换
其中i从 1 开始,pos是交换的目标位置(从 1 开始计数的下标),X是找到的最小值。 - 最后一行输出
Sorted array:后跟最终排好序的数组。
样例输入
5
5 3 8 1 2
样例输出
Initial: 5 3 8 1 2
Round 1: 找到最小值 1,与位置 1 交换
Round 2: 找到最小值 2,与位置 2 交换
Round 3: 找到最小值 3,与位置 3 交换
Round 4: 找到最小值 5,已在正确位置,无需交换
Sorted array: 1 2 3 5 8
样例解释
- 初始:
[5,3,8,1,2] - 第1轮:在下标1~5中找最小值为1(下标4),与下标1交换 →
[1,3,8,5,2] - 第2轮:在下标2~5中找最小值为2(下标5),与下标2交换 →
[1,2,8,5,3] - 第3轮:在下标3~5中找最小值为3(下标5),与下标3交换 →
[1,2,3,5,8] - 第4轮:在下标4~5中找最小值为5(下标4),已经在正确位置,无需交换。
- 最终有序。
要求
- 必须自己实现选择排序。
- 必须输出每轮的查找结果和交换情况。
- 注意输出格式中的空格和标点符号要和样例一致。