4 下列排序方法中，最坏情况下比较次数最少的是（　　）。A. 冒泡排序 B. 简单选择排序 C. 直接插入排序 D. 堆排序

考查要点：本题主要考查几种常见排序算法在最坏情况下的比较次数，要求学生掌握不同排序算法的时间复杂度特点。

解题核心思路：

1. 明确各排序算法的最坏时间复杂度：
   • 冒泡排序、简单选择排序、直接插入排序的最坏时间复杂度均为 $O(n^2)$，具体比较次数为 $\frac{n(n-1)}{2}$。
   • 堆排序的最坏时间复杂度为 $O(n \log n)$，显著优于前三种算法。
2. 比较最坏情况下的比较次数：
   堆排序的比较次数在最坏情况下仍为 $O(n \log n)$，而其他三种算法均为 $O(n^2)$，因此堆排序最优。

破题关键点：

• 区分不同排序算法的时间复杂度，尤其注意堆排序的高效性。
• 理解“最坏情况”对比较次数的影响，例如逆序数组对冒泡排序的影响。

各选项比较次数分析

A. 冒泡排序

• 最坏情况：数组元素完全逆序。
• 比较次数：$\frac{n(n-1)}{2}$。

B. 简单选择排序

• 最坏情况：每次比较均需遍历剩余元素。
• 比较次数：$\frac{n(n-1)}{2}$。

C. 直接插入排序

• 最坏情况：数组元素完全逆序。
• 比较次数：$\frac{n(n-1)}{2}$。

D. 堆排序

• 最坏情况：构建堆和调整堆的总时间。
• 比较次数：$O(n \log n)$，具体为 $O(n \log n)$ 级别，远小于 $O(n^2)$。

结论

在最坏情况下，堆排序的比较次数最少，因此正确答案为 D。