排序算法之：图书馆排序（Library Sort）的间隙维护机制与动态平衡策略 题目描述 图书馆排序（Library Sort），也称为间隙排序（Gap Sort），是一种基于插入排序的改进算法，通过在数组中预留间隙（Gaps）来减少插入操作时的元素移动次数。题目要求：实现图书馆排序的间隙维护机制，并分析其在动态插入过程中的平衡策略，确保排序的时间复杂度接近O(n log n)。 解题过程 基本思想 图书馆排序在初始数组中插入间隙（例如，每两个元素之间留一个空位），使得后续插入新元素时，只需局部移动元素，避免大规模数据搬迁。 间隙密度需动态调整：当间隙不足时，通过重新分配空间来平衡间隙分布。 间隙初始化 假设初始数组长度为 n ，扩展数组长度为 m = 2n ，即每个元素后预留一个空位（间隙）。 示例：初始数组 [3, 1, 2] 扩展为 [3, _, 1, _, 2, _] （ _ 表示间隙）。 插入过程与间隙维护 步骤1 ：使用二分查找确定新元素应插入的位置（忽略间隙，仅对实际元素排序）。 例如：向 [3, _, 1, _, 2, _] 插入元素 0 ，实际元素为 [1, 2, 3] ，二分查找确定 0 应插入最前。 步骤2 ：检查目标位置是否为间隙。若是，直接插入；否则，将最近间隙移动到目标位置附近： 若目标位置无间隙，向右（或左）搜索最近的间隙，将该间隙与目标位置之间的元素整体移动一位，腾出空位。 示例：插入 0 时，目标位置为索引0（当前是元素 1 ），向右找到最近间隙在索引1，将 [1, 2, 3] 右移一位，得到 [0, 1, _, 2, _, 3, _] 。 动态平衡策略 间隙耗尽判定 ：当间隙密度低于阈值（如50%），触发再平衡。 再平衡操作 ： 将所有实际元素紧凑排列到数组左侧。 重新分配间隙，例如在每两个元素之间插入一个间隙，恢复初始间隙密度。 示例：若数组变为 [0, 1, 2, 3] （无间隙），再平衡后为 [0, _, 1, _, 2, _, 3, _] 。 复杂度分析 每次插入的均摊成本为O(log n)（二分查找 + 局部移动），整体复杂度O(n log n)。 空间复杂度为O(n)（用于存储间隙）。 关键优化 间隙搜索优化：记录间隙位置，避免每次线性扫描。 再平衡阈值选择：根据实际负载动态调整阈值，避免频繁再平衡。 总结 图书馆排序通过预留间隙减少插入成本，其核心在于动态维护间隙密度。再平衡策略确保了算法在长期插入操作下的效率，适用于需要频繁插入的动态排序场景。