💡 真题解析

【答案】错误

【考纲知识点】排序算法(插入排序)

【解析】插入排序的时间复杂度在平均情况下为O(n²)，最好情况下的时间复杂度为O(n)，最坏情况下的时间复杂度为O(n²)。这是因为：

平均情况：当待排序数组中的元素分布较为均匀时，插入排序需要进行的比较次数大约是输入规模的一半，即O(n²)。

最好情况：如果待排序数组已经是有序的，那么插入排序只需进行n-1次比较即可完成排序，此时的时间复杂度为O(n)。

最坏情况：当待排序数组是完全逆序的，即所有元素都比前一个元素大（或小），此时需要进行的比较次数达到最大，即1+2+3+…+N-1，总次数为N(N-1)/2，因此时间复杂度为O(n²)。