难度：入门。题目原型为洛谷 U230326。本题考察选择排序的基本模板：每一轮从未排序区间选出最小元素，与未排序区间的第一个位置交换。

目标

完成本题后，你应该能够：

• 手写选择排序的完整两层循环，并解释外层 i、内层 j 各自的作用；
• 说清「最小下标 minj」如何逐步定位未排序区间的最小值；
• 独立输出排序后的数组，不借助 std::sort。

前置知识

• 10.2 选择排序的思想：从未排序区间选最小，放到已排序区间的末尾；
• 一维数组与 swap 交换两个元素。

题目

读入 n 和 n 个整数，用选择排序将它们从小到大排序，输出排序后的结果。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，空格分隔。

输出格式

一行 n 个整数，空格分隔，表示排序后的数组。

数据范围

项目	范围
数组长度 n	1 ≤ n ≤ 10⁴
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

5
3 1 4 1 5

样例输出

1 1 3 4 5

样例解释

3 1 4 1 5 选择排序后为 1 1 3 4 5，注意两个 1 都要保留。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-10/exercise/E-10-06-selection-sort-template
pnpm lab:score -- labs/chapter-10/exercise/E-10-06-selection-sort-template

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 升序、降序、含重复值三种情况都通过
• 能说出外层循环为什么只需要到 n - 2（最后一轮只剩一个元素必然就位）

思考题

1. 选择排序每一轮都只做一次交换，那它是不是「交换次数最少」的排序算法？为什么？
2. 如果输入已经有序，选择排序仍会做多少次比较？会做多少次交换？

题解

点击查看题解

思路

选择排序把数组分成「已排序前缀」和「未排序后缀」：

1. 外层 i 表示当前要确定的位置，从 0 到 n - 2；
2. 内层从 i 开始扫描未排序区间 [i, n-1]，记录最小元素的下标 minj；
3. 把 a[i] 与 a[minj] 交换，位置 i 就固定下来。

因为每一轮只交换一次，所以选择排序的交换次数是 O(n)，但比较次数始终是 n(n-1)/2。

复杂度分析

• 时间复杂度：O(n²)，比较次数固定为 n(n-1)/2；
• 空间复杂度：O(1) 额外空间（原地排序）。