排序算法之：Smoothsort（平滑排序）的自适应堆构建与性能分析

题目描述
Smoothsort是一种基于堆结构的自适应排序算法，由Edsger Dijkstra提出。它的时间复杂度在最好情况下为O(n)（当输入已排序时），最坏情况下为O(n log n)，且是原地排序。其核心思想是通过一种特殊的堆结构（Leonardo堆）动态调整堆的大小，使得在输入数据部分有序时减少比较和交换次数。

解题过程

1. 理解Leonardo数

   • Leonardo数序列定义为：
     L(0) = 1, L(1) = 1, L(k) = L(k-1) + L(k-2) + 1（k ≥ 2）。
     例如：1, 1, 3, 5, 9, 15, 25, ...
   • 性质：任意正整数可以唯一表示为若干个互不相同的Leonardo数之和（类似二进制表示，但需满足相邻Leonardo数索引差≥2）。

2. Leonardo堆的构建

   • 堆由多个Leonardo树（类似平衡二叉树）组成，每棵树的大小对应一个Leonardo数。
   • 每棵树满足最大堆性质：根节点值 ≥ 子节点值。
   • 树的构建规则：
     • 大小为L(k)的树由根节点、左子树（大小L(k-1)）和右子树（大小L(k-2)）组成。
     • 右子树索引必须紧邻根节点，左子树在右侧子树之前。

3. 排序步骤

   • 阶段1：建堆
     从左到右扫描数组，动态维护Leonardo堆：
     • 若当前元素可合并到堆中（符合Leonardo数组合规则），则调整堆结构。
     • 合并时比较相邻树的根节点，将较大的根节点上移，确保堆性质。
   • 阶段2：提取最大值
     重复将堆的最大值（最右侧树的根）与堆末尾交换，缩小堆范围，重新调整堆结构。

4. 调整堆的细节

   • 当移除最大值后，原堆分裂为多个子树。
   • 对剩余部分递归调整，确保每棵树仍满足堆性质。
   • 调整时比较根节点与其子节点，若子节点更大则交换，并递归检查子树。

5. 自适应性能分析

   • 若输入已排序，建堆阶段仅需O(n)比较（无需调整堆）。
   • 最坏情况下（完全逆序），需O(n log n)比较，但常数因子优于传统堆排序。

示例
对数组 [3, 1, 4, 1, 5, 9, 2, 6]：

1. 建堆后形成Leonardo堆结构（如大小为3和5的树）。
2. 依次提取最大值9、6、5...，每次调整堆。
3. 最终得到升序序列。

关键点

• Smoothsort通过灵活组合Leonardo堆，减少对有序数据的冗余操作。
• 需注意Leonardo数的唯一分解性质，确保堆合并与分裂的正确性。