【考纲知识点】插入排序的时间复杂度、适用场景及算法特性

【正确答案】C

【题目解析】

插入排序的特性：

时间复杂度：

最好情况（数据几乎有序）：O(n)，只需少量比较和移动。

最坏情况（数据逆序）：O(n²)，需大量比较和移动。

空间复杂度：O(1)，原地排序。

稳定性：稳定（不改变相同元素的相对顺序）。

选项分析：

A.数据量大且乱序严重：插入排序在最坏情况下效率极低（O(n²)），不适合大规模乱序数据。此时快速排序、归并排序等O(nlogn)算法更优。

B.稳定排序但不要求实时性：插入排序虽稳定，但O(n²)的时间复杂度在数据量大时效率不足。若不要求实时性，归并排序（稳定且O(nlogn)）是更好选择。

C.数据几乎有序：插入排序在此场景下表现极佳（接近O(n)），只需少量插入操作即可完成排序。

D.交换次数最少排好大数组：插入排序的交换次数不一定最少（如，逆序数组需多次交换）。选择排序在交换次数上更优（O(n)次交换），但整体效率仍为O(n²)。

因此正确答案为C。