【考纲知识点】选择排序的时间复杂度分析、算法稳定性

【正确答案】√

【题目解析】

选择排序的核心逻辑：

将数组分为已排序和未排序两部分，每轮从未排序部分中选择最小元素，与未排序部分的第一个元素交换。

无论数组初始状态如何，每轮都需遍历未排序部分的所有元素，确定最小值。

比较次数分析：

第1轮：比较n-1次 

第2轮：比较n-2次 

...

第n-1轮：比较 1次 

总比较次数：

关键点验证：

与初始状态无关：无论数组是否有序，每轮遍历的元素数量固定，比较次数始终为O(n²)。

对比其他排序：

冒泡排序：若数组已有序，可通过标志位提前终止，最好情况为O(n)。

插入排序：若数组接近有序，比较次数接近O(n)。

选择排序：无优化可能，始终为O(n²)。

结论：选择排序的比较次数与初始数组状态无关，始终为O(n²)，答案为√。