题2
题目
Q:在待排序的元素序列基本有序的前提下, 效率最高的排序算法是 ( ).
A. 直接插入排序
B. 简单选择排序
C. 快速排序
D. 归并排序
分析
A:直接插入排序的复杂度不是总是 O(n)， 它在最好情况下才是 O(n)。
- O(n)： 最好情况，序列已经有序
- O(n^2)： 平均情况和最坏情况，序列无序或部分有序
理解 O(n) 的条件： - 最好情况： 当待排序序列已经是完全有序的时候，直接插入排序的复杂度为 O(n)。
- 原因： 因为每次插入新元素时，它都正好位于它应该在的位置。比如，如果序列是 1, 2, 3, 4, 5，插入 6 时，只需要比较一次就知道它应该放在最后，不需要进行任何移动，时间复杂度仅仅与元素个数 n 成正比。
为什么其他情况下不是 O(n)： - 平均情况和最坏情况： 当待排序序列不是完全有序时，直接插入排序的时间复杂度就不是 O(n) 了。
- 原因： 在平均情况和最坏情况下，插入新元素时可能需要进行大量的比较和移动操作。 最坏情况下，比如序列是逆序排列的，每次插入都需要比较 n-1 次，时间复杂度为 O(n^2)。
解
A
由于序列初始基本有序,因此使用直接插入排序算法的时间复杂度接近
- 直接插入排序： 直接插入排序对于基本有序的序列非常高效，因为每次插入操作只需要进行少量比较和移动。时间复杂度接近 O(n)，效率很高。
- 简单选择排序： 简单选择排序每次都要找到未排序序列中的最小值，再进行交换。这种算法的时间复杂度为 O(n^2)，与数据是否有序关系不大，效率较低。
- 快速排序： 快速排序是一种划分交换排序，它会选择一个基准元素，将序列划分为两个部分，然后递归地对两个部分进行排序。虽然快速排序在平均情况下时间复杂度为 O(n log n)，但在最坏情况下（比如序列已经是排序好的）会退化到 O(n^2)，效率会下降。
- 归并排序： 归并排序是一种分治排序。它将序列递归地分成两个子序列，分别排序后合并。归并排序的时间复杂度始终为 O(n log n)，与数据是否有序无关，效率较高，但相对于直接插入排序，它需要额外的空间进行合并操作。