各排序算法比较次数详细分析

1. 冒泡排序 - O(n²)

算法过程：

• 相邻元素两两比较，大的往后移
• 每趟确定一个最大值到末尾

最坏情况： 完全逆序 [5,4,3,2,1]

第1趟：比较 n-1 次（5和4,4和3,3和2,2和1）
第2趟：比较 n-2 次（前n-1个元素）
第3趟：比较 n-3 次
...
第n-1趟：比较 1 次

总比较次数 = (n-1)+(n-2)+...+1 = n(n-1)/2

示例计算： n=5时，比较次数 = 4+3+2+1 = 10 = 5×4/2

---

2. 简单插入排序 - O(n²)

算法过程：

• 将第i个元素插入到前i-1个已排序元素中
• 从后向前比较，找到合适位置

最坏情况： 完全逆序 [5,4,3,2,1]

插入第2个元素：比较1次
插入第3个元素：比较2次（与前2个都要比）
插入第4个元素：比较3次
...
插入第n个元素：比较n-1次

总比较次数 = 1+2+3+...+(n-1) = n(n-1)/2

示例： 插入[4]到[5]中需1次比较，插入[3]到[5,4]中需2次比较…

---

3. 简单选择排序 - O(n²)

算法过程：

• 第i趟从n-i+1个元素中选出最小值
• 放到第i个位置

任何情况下：（比较次数固定）

第1趟：从n个元素中选最小，比较 n-1 次
第2趟：从n-1个元素中选最小，比较 n-2 次
第3趟：从n-2个元素中选最小，比较 n-3 次
...
第n-1趟：从2个元素中选最小，比较 1 次

总比较次数 = (n-1)+(n-2)+...+1 = n(n-1)/2

特点： 比较次数与初始序列无关，始终是n(n-1)/2

---

4. 快速排序 - 最坏O(n²)，平均O(nlogn)

算法过程：

• 选择pivot，分区（小的在左，大的在右）
• 递归排序左右两部分

最坏情况： pivot总是最大/最小值（如已排序数组）

第1次分区：比较n-1次，分成0个和n-1个
第2次分区：比较n-2次，分成0个和n-2个
第3次分区：比较n-3次
...

总比较次数 = (n-1)+(n-2)+...+1 = n(n-1)/2

平均情况： pivot接近中位数

递归深度：log n
每层总比较：约n次
总比较次数：n log n

---

5. 堆排序 - O(nlogn) ⭐ 关键差异

算法过程：

1. 建立大顶堆
2. 交换堆顶与末尾，调整堆

建堆阶段：

从第⌊n/2⌋个节点开始向下调整
每个节点最多比较 2×高度 次
总比较次数 ≈ 2n（可证明为O(n)）

排序阶段：

进行n-1次：
- 交换堆顶与末尾（0次比较）
- 调整堆顶元素下沉（最多2log n次比较）

总比较次数 = (n-1) × 2log n ≈ 2n log n

总计： 2n + 2n log n ≈ 2n log n

为什么是nlogn而不是n²？

• 堆是完全二叉树，高度为log n
• 每次调整只需沿一条路径比较，不是比较所有元素
• 路径长度最多log n，每层最多2次比较

---

总结对比

排序算法	最坏情况比较次数	复杂度
冒泡排序	n(n-1)/2	O(n²)
插入排序	n(n-1)/2	O(n²)
选择排序	n(n-1)/2	O(n²)
快速排序（最坏）	n(n-1)/2	O(n²)
堆排序	2n log n	O(n log n)

堆排序利用了堆的树形结构特性，避免了O(n²)的比较，这是它与其他简单排序算法的本质区别。