给定递增整数数组，求各排序算法降序排列的比较次数

首先明确：插入排序完全可以完成降序排列，只需将原升序逻辑中的比较条件反转（比如原升序是if (A[j] > current)就后移元素，降序则改为if (A[j] < current)后移），核心逻辑不变，仅调整判断方向。

1. 插入排序（Insertion Sort） #

输入为严格递增数组时，属于插入排序的最坏情况——每个新元素都需要和前面所有已排序元素逐一比较。

• 总比较次数：第i个元素（从第2个开始，索引从1计数）需比较i次，总和为 1 + 2 + ... + (n-1) = n(n-1)/2 次。

2. 快速排序（Quick Sort） #

以经典的“选最左/最右元素为基准”的实现为例，严格递增数组会触发最坏情况：每次划分后基准会被放到数组一端，导致其中一个子数组为空，另一个子数组包含剩余全部元素。

• 总比较次数：每次划分需遍历当前子数组所有元素，总次数为 n(n-1)/2 次。
  注：若采用随机选择基准的优化版快速排序，平均情况比较次数为O(nlogn)，但本题是最坏输入场景，因此为平方级。

3. 选择排序（Selection Sort） #

选择排序的逻辑是每次在未排序区间找到最大元素（降序需求），放到已排序区间末尾。无论输入是否有序，它的比较次数都是固定的：

• 第i轮（从0到n-2）需比较 n-1-i 次，总次数为 (n-1) + (n-2) + ... + 1 = n(n-1)/2 次。

4. 堆排序（Heap Sort） #

堆排序分为构建最大堆、依次取出堆顶并调整堆两个阶段：

• 构建最大堆：从最后一个非叶子节点开始向上调整，总比较次数约为2n（精确值为2(n - log₂(n+1))，通常简化为O(n)）。
• 调整堆：每次取出堆顶后，调整堆结构需logk次比较（k为当前堆的大小），n-1次调整的总比较次数约为nlogn。
• 总比较次数：整体为O(nlogn)级别，近似值为nlog₂(n)。

内容的提问来源于stack exchange，提问作者siddharth1000