C++求数组第二小值：两次选择法实现及代码解析

根据您的要求，我将使用 **C++** 实现这个“找出数组中第二小值”的算法。题目提示使用**两次选择排序交换**的思路，既清晰又符合要求。 --- ## 🧩 解题思路 1. **第一轮**：从 `a[1]` 到 `a[n]` 中找到最小值，与 `a[1]` 交换（此时 `a[1]` 为全局最小）。 2. **第二轮**：从 `a[2]` 到 `a[n]` 中找到最小值，与 `a[2]` 交换（此时 `a[2]` 为剩余元素中的最小，即全局第二小）。 3. 输出 `a[2]`。 > ⚠️ 注意：题目输入样例中数组下标从 1 开始，但 C++ 数组默认从 0 开始，我会在实现中做相应调整，保证逻辑一致。 --- ## 💻 完整代码实现 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int a[100]; // 根据题目 n < 100 for (int i = 0; i < n; i++) { cin >> a[i]; } // 第一次选择：找最小值放到 a[0] int minIdx = 0; for (int i = 1; i < n; i++) { if (a[i] < a[minIdx]) { minIdx = i; } } swap(a[0], a[minIdx]); // 第二次选择：从 a[1] 开始找最小值放到 a[1] minIdx = 1; for (int i = 2; i < n; i++) { if (a[i] < a[minIdx]) { minIdx = i; } } swap(a[1], a[minIdx]); // 输出第二小的值 cout << a[1] << endl; return 0; } ``` --- ## ✅ 代码详解 | 步骤 | 说明 | |------|------| | **输入部分** | 读取 `n` 和 `n` 个整数，存入数组 `a`。 | | **第一轮查找** | 从下标 `0` 开始，遍历找到最小值下标，并与 `a[0]` 交换。 | | **第二轮查找** | 从下标 `1` 开始（跳过已确定的全局最小），找到剩余最小值，与 `a[1]` 交换。 | | **输出** | 直接输出 `a[1]`，即为次小值。 | > 使用 `swap` 函数需要包含 `<iostream>` 或 `<utility>`，此处 `using namespace std;` 已提供支持。 --- ## 🧪 测试样例 **输入：** ``` 5 4 3 5 2 6 ``` **运行过程：** - 第一次：最小值 2，与 a[0]（4）交换 → `[2, 3, 5, 4, 6]` - 第二次：从 a[1] 开始，最小值 3，与 a[1]（3）交换 → 不变 - 输出：`3` **输出：** ``` 3 ``` --- ## 💡 开发建议与注意事项 - **边界情况**：如果 `n < 2`，则不存在第二小值，建议提前判断并处理（例如输出提示或报错）。 - **重复值处理**：如果数组中有重复的最小值，例如 `[1, 1, 2]`，该算法会正确输出 `1`，因为第二次查找会找到另一个 `1`。 - **时间复杂度**：两轮遍历均为 O(n)，总复杂度 O(n)，空间复杂度 O(1)，完全满足题目要求（n<100）。 - **可扩展性**：如果要求第 k 小值，可以复用选择排序的概念，进行 k 次选择，但要注意 k 不要过大以避免性能下降（此时可考虑快速选择或堆）。 --- ## 📚 相关学习资源 - [C++ 标准库 swap 函数文档](https://en.cppreference.com/w/cpp/algorithm/swap) - [选择排序算法详解](https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F) - [数组与指针基础](https://en.cppreference.com/w/cpp/language/array) --- ######[AI写代码神器 | 1007点数解答 | 2026-08-21 19:31:55]