✏️ 纠错
第 249 题 / 共 301 题
第8题 以下C++代码，尝试对有n个整数的数组arr进行排序。这个代码实现了选择排序算法。
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
swap(arr[i], arr[minIndex]);
}你真棒！
📝 题目解析
【考纲知识点】选择排序的实现原理、时间复杂度分析、数组操作
【正确答案】√
【题目解析】
选择排序的核心思想：
将数组分为已排序和未排序两部分，初始时已排序部分为空。
每轮从未排序部分中选择最小元素，与未排序部分的第一个元素交换位置，逐步扩大已排序部分。
代码流程分析：
外层循环（i从0到n-2）：控制当前未排序部分的起始位置。
内层循环（j从i+1到n-1）：遍历未排序部分，找到最小值的索引minIndex。
交换操作：若minIndex不等于i，则交换arr[i]与arr[minIndex]，将最小值放到已排序部分末尾。
关键点验证：
最小值选择：内层循环确保minIndex指向未排序部分的最小元素。
边界处理：外层循环到n-2为止，因为最后一个元素会在前面的迭代中自然排好。
避免冗余交换：通过if (minIndex != i)判断，避免自我交换。
时间复杂度：
无论数据初始状态如何，均需进行两轮嵌套循环，时间复杂度为O(n2)。
结论：该代码严格遵循选择排序的算法逻辑，正确实现了选择排序，因此答案为正确。