基于两次选择排序求第二小值（Python实现）

根据您的描述，这里实际上是要**执行两次选择排序的部分步骤**，找到第二小的值。由于题目要求按照两次交换的方式实现，我们直接按此逻辑处理。 ### 🧠 思路分析 - 第一轮：从 a[1]~a[n] 中找到最小值，与 a[1] 交换； - 第二轮：从 a[2]~a[n] 中找到最小值，与 a[2] 交换； - 此时 a[2] 就是第二小的值。 这种方式类似选择排序前两步，但**不要求完全排序**。 ### 💻 参考代码（Python） ```python n = int(input()) arr = list(map(int, input().split())) # 注意：Python 下标从0开始，题目中a[1]对应arr[0] # 第一轮：找全局最小值，交换到位置0 min_idx = 0 for i in range(1, n): if arr[i] < arr[min_idx]: min_idx = i arr[0], arr[min_idx] = arr[min_idx], arr[0] # 第二轮：从下标1开始找最小值，交换到位置1 min_idx = 1 for i in range(2, n): if arr[i] < arr[min_idx]: min_idx = i arr[1], arr[min_idx] = arr[min_idx], arr[1] # 输出第二小值 print(arr[1]) ``` ### 🧪 运行示例 **输入：** ``` 5 4 3 5 2 6 ``` **过程：** - 初始：[4, 3, 5, 2, 6] - 第一轮找到最小值 2（下标3），交换到位置0 → [2, 3, 5, 4, 6] - 第二轮从下标1开始，找最小值为3（本身），无需交换 → [2, 3, 5, 4, 6] - 输出 arr[1] = 3 **输出：** `3` ✅ ### ⚠️ 边界情况与注意事项 - **n < 100**，但可能 **n < 2** 时，题目未明确约束，但逻辑上需要至少两个元素才能谈“第二小”。假设 n ≥ 2。 - **重复值问题**：如果数组中有重复的最小值（如 [1,1,2]），此算法仍能正确输出第二小值（2），因为第一次交换后，a[1] 仍是 1 情况不会发生——实际上第二次从下标1开始找最小，会忽略第一个最小值，得到下一个非最小（或同样最小但位置不同）。测试： - 输入：3 / 1 1 2 → 第一轮后 [1,1,2]，第二轮从下标1找到最小1（下标1），交换后不变，输出 a[1]=1，但第二小应为1（正确）。 - **若题目要求输出严格第二小（即排除重复）**，则需额外处理，但根据题目描述，这里采用“按位置”方式实现，即允许重复值。 ### 📌 开发建议 - 此方法时间复杂度 O(n)，空间 O(1)。 - 如果想用更通用的“不交换数组”方式，可直接两次遍历找最小和次小，但交换方法易于理解且符合题目提示。 - 实际开发中，可用 `sorted(arr)[1]` 快速实现，但这里主要考察排序思想。 ######[AI写代码神器 | 771点数解答 | 2026-08-21 19:27:22]