堆排与希尔排序速览

堆排与希尔排序速览

一、面试常考点

1. 堆排序

• 时间复杂度：O(n log n)。
• 空间复杂度：O(1)（原地）。
• 稳定性：不稳定。（深入阅读：1. 堆排）

2. 希尔排序

本质是“分组插入排序”，通过缩小增量提升效率，理论分析较复杂，工程里较少作为首选。（深入阅读：2. 希尔排序）

二、应用场景

1. 堆排

内存敏感、需要原地排序时可选。

2. 希尔排序

面试中多作为“了解型”问题，重点说思想和与插入排序的关系。