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

考查要点：本题主要考查几种常见排序算法在最坏情况下的时间复杂度，特别是比较次数的比较。

解题核心思路：

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

破题关键点：

• 区分不同排序算法的时间复杂度特性，尤其关注最坏情况下的表现。
• 理解堆排序通过构建堆和调整堆操作实现高效排序，避免了其他算法可能出现的“完全逆序”情况下的高比较次数。

各选项分析

A. 冒泡排序

• 最坏时间复杂度：$O(n^2)$
• 比较次数：当数组完全逆序时，需比较$\frac{n(n-1)}{2}$次。

B. 简单选择排序

• 最坏时间复杂度：$O(n^2)$
• 比较次数：无论数组是否有序，均需比较$\frac{n(n-1)}{2}$次（每次需遍历未排序部分找最小值）。

C. 直接插入排序

• 最坏时间复杂度：$O(n^2)$
• 比较次数：当数组完全逆序时，需比较$\frac{n(n-1)}{2}$次。

D. 堆排序

• 最坏时间复杂度：$O(n \log n)$
• 比较次数：
  1. 构建堆：$O(n)$（实际约为$2n$次比较）。
  2. 提取最大值：共$n-1$次堆调整，每次需$\log n$次比较，总计$O(n \log n)$。
     总比较次数为$O(n \log n)$，远小于其他三种算法的$O(n^2)$。