排序算法之：Smoothsort（平滑排序）的堆构建与自适应性能分析 题目描述 Smoothsort是一种由Edsger Dijkstra发明的基于堆结构的自适应排序算法。它结合了堆排序的高效性和插入排序在部分有序数据上的优势，其时间复杂度在最佳情况下为O(n)，最坏情况下为O(n log n)。本题要求你理解Smoothsort的核心堆结构（Leonardo堆）的构建过程，并分析其自适应性能的原理。 解题过程 理解Leonardo数 Leonardo数是Smoothsort的基础，定义如下： L(0) = 1, L(1) = 1, L(k) = L(k-1) + L(k-2) + 1（k ≥ 2）。 例如：L(2)=3, L(3)=5, L(4)=9, L(5)=15。 性质：任意正整数可唯一表示为若干个互不相同的Leonardo数之和（类似二进制表示，但需满足相邻L(k)的索引差≥2）。 Leonardo堆的结构 Smoothsort将数组划分为多个Leonardo堆（每个堆的大小为某个L(k)），这些堆满足以下条件： a. 每个堆是一个最大堆（父节点 ≥ 子节点）。 b. 堆的大小按降序排列，且相邻堆的根节点值递增（即后一个堆的根 ≥ 前一个堆的根）。 示例：数组大小为11时，可表示为L(4)=9 + L(2)=3（因为9+3=12>11，不合法）或L(3)=5 + L(2)=3 + L(1)=1 + L(0)=1（5+3+1+1=10 <11，需调整）。实际需动态调整。 堆的构建过程（排序阶段） 步骤1：初始化堆序列 从左到右扫描数组，逐步扩展Leonardo堆，确保堆序列满足上述条件。具体步骤： 若当前元素可加入前一个堆（通过扩展堆大小），则合并（需调整堆结构）。 否则，新建一个大小为L(1)=1的堆。 步骤2：调整堆结构 当新建或合并堆时，需保证最大堆性质： a. 比较当前堆的根节点与其左右子堆的根（子堆大小由L(k-1)和L(k-2)决定）。 b. 若子堆的根更大，则交换根与较大子堆的根，并递归调整被交换的子堆。 示例：对数组[ 4, 2, 7, 1, 5 ]： 初始堆序列：[ 4 ]（大小L(1)=1）。 加入2：新建堆[ 2]（大小L(1)=1），此时堆序列为[ 4], [ 2]，但需满足根递增（4>2不满足），故交换根节点，变为[ 2], [ 4 ]。 加入7：新建堆[ 7]，序列为[ 2], [ 4], [ 7]（根2<4 <7，满足）。 加入1：尝试合并堆，但无法直接合并，新建堆[ 1]，序列为[ 2], [ 4], [ 7], [ 1]（根7>1不满足），交换后为[ 2], [ 4], [ 1], [ 7 ]。 继续调整至所有元素加入。 排序与自适应性能分析 排序阶段 ：重复移除最大元素（堆序列的最后一个根），重新调整堆序列。 a. 移除最大元素后，将其与堆序列末尾交换。 b. 调整剩余堆：若最后一个堆被移除后，前一个堆的大小可拆分（如L(k)拆为L(k-1)和L(k-2)），则拆分并调整子堆。 自适应性 ： 若输入数组已有序，Smoothsort仅需构建一次堆序列（无需调整），时间复杂度为O(n)。 最坏情况（完全逆序）需频繁调整堆，复杂度为O(n log n)。 优势：在部分有序数据上，减少堆调整次数，优于传统堆排序。 关键点总结 Smoothsort通过Leonardo堆的动态组合适应数据分布。 自适应性能源于堆序列的稳定性：当数据有序时，堆结构几乎不需要调整。 实现时需注意堆的合并/拆分条件和递归调整策略。