对长度为 n 的线性表排序，在最坏情况下，比较次数不是 n（n－ 1） /2 的排序方法是（ ）。A. 快速排序B. 冒泡排序C. 直接插入排序D. 堆排序

本题主要考察常见排序算法在最坏情况下的比较次数，需明确各排序算法的时间复杂度特征。

关键知识点：各排序算法的最坏比较次数

排序算法的最坏时间复杂度通常对应最坏情况下的比较次数，公式 $\frac{n(n-1)}{2}$ 对应时间复杂度 $O(n^2)$。

1. 快速排序（A选项）

快速排序的核心是通过基准元素将数组分成两部分。最坏情况（如数组已有序，且每次选择第一个或最后一个元素作为基准）下，每次划分仅减少一个元素，递归深度为 $n$，比较次数为 $\frac{n(n-1)}{2}$，符合 $O(n^2)$。

2. 冒泡排序（B选项）

冒泡排序通过相邻元素比较交换实现排序。最坏情况（数组逆序）下，每轮需比较 $n-i$ 次（$i$ 为轮轮轮数），总比较次数为 $1+2+\dots+(n-1)=\frac{n(n-1)}{2}$，符合 $O(n^2)$。

3. 直接插入排序（C选项）

直接插入排序将元素逐个插入已排序序列。最坏情况（数组逆序）下，每个元素需与前面所有元素比较，总比较次数为 $1+2+\dots+(n-1)=\frac{n(n-1)}{2}$，符合 $O(n^2)$。

4. 堆排序（D选项）

堆排序利用堆（完全二叉树）的性质，通过堆化操作排序。最坏情况下，每次堆化的时间复杂度为 $O(\log n)$，总比较次数为 $O(n\log n)$，远小于 $\frac{n(n-1)}{2}$。