时间复杂度是正确的总结如下堆排序Heap Sort平均时间复杂度O(n log n)最坏时间复杂度O(n log n)原因建堆需 O(n)之后 n 次取最大或最小并调整堆每次调整为 O(log n)故总为 O(n log n)堆结构保证了最坏情况也不会退化。快速排序Quick Sort平均时间复杂度O(n log n)期望意义下基准随机或三数取中时最坏时间复杂度O(n²)如每次选到最小/最大元素作基准数组已有序且未随机化可通过随机化基准或三数取中等优化避免最坏情况。冒泡排序Bubble Sort平均与最坏均为 O(n²)最好情况已排序可优化至 O(n)加提前终止标志但最坏逆序需 n(n−1)/2 次比较和交换。选择排序Selection Sort平均、最坏、最好时间复杂度均为 O(n²)因为每轮固定找一个极值比较次数恒为 ∑(i1 to n−1) (n−i) n(n−1)/2与输入顺序无关。补充说明空间复杂度方面堆排序和选择、冒泡均为 O(1)原地排序快排递归栈深度平均 O(log n)最坏 O(n)若不使用尾递归优化或迭代实现。稳定性仅堆排序和快排不稳定冒泡和选择排序在标准实现中稳定但选择排序通常不稳定除非特别设计——注意标准选择排序不稳定因交换可能破坏相等元素相对顺序冒泡若只在a[i] a[i1]时交换则稳定。✅ 正确结论您对各算法最坏/平均时间复杂度的判断准确默认指标准实现。根本差异在于算法对输入数据分布的敏感性即控制流程是否依赖于输入元素的相对大小关系尤其是划分质量具体体现在以下三方面1.结构保证性 vs. 划分依赖性堆排序基于完全二叉树的堆结构隐式数组表示其核心操作heapify向下调整的时间由树高决定——无论输入如何堆的高度恒为 ⌊log₂n⌋。✅ 每次extract-max后的调整最多执行 log n 层比较与交换建堆过程自底向上heapify可证明总时间为 O(n)非直觉的 O(n log n)。→最坏路径长度被数据结构严格上界约束与输入顺序无关。快排核心是分区partition其效率完全取决于每次选中的基准pivot能否将数组大致等分。❌ 若基准总是极值如已排序数组中选首/尾元素则每次仅减少一个元素递归深度达 n 层每层需 O(n) 比较 → 总耗时 O(n²)。→性能强依赖于划分的平衡性而平衡性由输入分布和 pivot 策略共同决定无结构保障。2.计算模型的确定性堆排序是确定性算法同一输入、同一实现执行路径唯一时间复杂度恒定。快排标准版是输入敏感型确定性算法不同输入导致不同递归树形状最坏输入如单调序列 固定首元素 pivot可被明确构造。 类比堆排序像“按固定楼梯逐级下楼”每步高度≤log n快排像“找路下山”若总往死胡同走bad pivot就会绕远路O(n²)。3.数学本质差异维度堆排序快排最坏递归式T(n) T(n−1) O(log n) → 解得 O(n log n)T(n) T(n−1) O(n) → 解得 O(n²)主定理适用不直接适用非分治形式但可拆解为建堆 O(n) n 次 O(log n) 调整最坏满足主定理 Case 3a1, b1 ⇒ T(n)Θ(n²)下界突破可能无法低于 Ω(n log n)比较排序下界最坏无法避免除非改变 pivot 策略如随机化、中位数中位数✅ 结论堆排序的 O(n log n) 是结构刚性保障的结果快排的 O(n²) 是其分治策略在最坏划分下的自然退化二者差异源于“是否将性能锚定在最坏输入可构造的划分质量上”。