P1205 选择排序-升序排列

暂无评定 传统题 GESP数组排序循环结构 上传者
时间限制1000ms
内存限制256MiB
通过 / 提交0/0

P1205选择排序-升序排列

暂无评定 传统题 GESP数组排序循环结构 上传者
时间限制1000ms
内存限制256MiB
通过 / 提交0/0

故事引入
老师让同学们把数字卡片按从小到大排好。小竞用了“选择排序”的方法:
每一轮,她先找出剩下的卡片中最小的那张,然后把它放到最前面。
这样,经过若干轮,所有的卡片就都有序了。
现在请你帮助小竞实现这个方法,并且把每一轮“选中的最小数字和谁交换”的过程记录下来。


题目描述

输入 n 个整数,使用选择排序将它们按从小到大(升序)排序。
要求:

  1. 每一轮(从第1轮到第n-1轮)都要输出本轮找出的最小值以及与哪个位置的元素交换。
  2. 如果最小值已经在正确的位置(即不需要交换),则输出“本轮无需交换”。
  3. 最后输出排序后的完整数组。

输入格式

第一行一个整数 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),已经在正确位置,无需交换。
  • 最终有序。

要求

  • 必须自己实现选择排序。
  • 必须输出每轮的查找结果和交换情况。
  • 注意输出格式中的空格和标点符号要和样例一致。