难度：进阶。题目原型为洛谷 B4171（私题）。本题只关心选择排序的交换次数：虽然比较次数是 O(n²)，但交换次数最多只有 n - 1，两者需要区分清楚。

目标

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

• 在选择排序循环中只统计「真正发生」的交换；
• 说明为什么交换次数是 O(n)，而时间复杂度仍是 O(n²)；
• 用 n ≤ 8000 的数据规模验证 O(n²) 算法可以接受。

前置知识

• 10.2 选择排序的实现；
• 时间复杂度的基本概念（比较次数 vs 交换次数）。

题目

读入 n 和 n 个整数。用选择排序将它们从小到大排序：每轮在未排序区间 [i, n-1] 中选出最小值，若该最小值不在当前位置 i，则与 a[i] 交换。输出整个排序过程中发生的总交换次数。

输入格式

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

输出格式

一行一个整数，表示总交换次数。

数据范围

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

样例

样例输入

6
5 6 4 2 1 3

样例输出

4

样例解释

选择排序共发生 4 次交换：5↔1、6↔2、4↔3、6↔4。最后一轮最小值已在当前位置，不交换。

如何验证

先安装 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-09-selection-sort-bcsp
pnpm lab:score -- labs/chapter-10/exercise/E-10-09-selection-sort-bcsp

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

完成清单

• 样例输出与题目一致
• 升序（0 次）、逆序、含重复值三种情况都通过
• 能说出为什么交换次数是 O(n) 但算法仍是 O(n²)

思考题

1. 逆序数组 n, n-1, ..., 1 在选择排序下的交换次数是多少？写出通项。
2. 既然交换次数是 O(n)，能不能据此把选择排序优化成 O(n log n)？为什么不能？

题解

点击查看题解

思路

每轮扫描 [i, n-1] 找到最小值下标 minj：

• minj == i：最小值已在当前位置，不交换；
• minj != i：交换一次并计数。

因为外层循环只有 n - 1 轮，每轮至多交换一次，所以交换次数 ≤ n - 1，即 O(n)。但寻找每轮最小值需要扫描，比较次数固定为 n(n-1)/2，因此整体仍是 O(n²)。

复杂度分析

• 时间复杂度：O(n²)（比较次数决定）；
• 空间复杂度：O(1) 额外空间；
• 交换次数：O(n)，最坏 n - 1 次。