排序算法之：图书馆排序（Library Sort）的插入优化策略 题目描述： 图书馆排序是一种改进的插入排序算法，通过在有元素之间预留一些空位（gap），来减少插入新元素时需要移动的元素数量。其核心思想类似于图书馆整理书籍时为新书预留空间。给定一个无序整数数组，请使用图书馆排序算法对其进行排序，并分析其时间复杂度和空间复杂度。 解题过程： 基本思想： 图书馆排序在数组中有意地插入一些空位，当需要插入新元素时，如果目标位置已有元素，可以利用附近的空位来减少大规模的元素移动。这类似于我们在书架上放书时，不会把书架塞满，而是留出一些空隙方便插入新书。 算法步骤： 步骤1：初始化 创建一个比原数组大的工作数组，大小为原数组的(1 + ε)倍（通常ε取1） 将工作数组的所有位置初始化为空（可以用特殊值表示） 步骤2：逐个插入元素 遍历原数组中的每个元素 使用二分查找在工作数组的已排序部分找到该元素的插入位置 如果目标位置为空，直接放入元素 如果目标位置已有元素，则向右或向左寻找最近的空位 如果附近没有空位，需要重新平衡：将元素均匀分布，重新创建空位 步骤3：重新平衡策略 当空位不足时（比如连续k个位置都没有空位），执行重新平衡 将当前所有元素均匀分布到工作数组中，在元素之间创建新的空位 重新平衡的频率影响算法效率，需要合理选择阈值 步骤4：压缩结果 排序完成后，将工作数组中的非空元素按顺序提取出来 得到最终的有序数组 详细示例： 假设排序数组为[ 5, 2, 8, 1 ]，工作数组大小为8： 初始工作数组：[_ , _ , _ , _ , _ , _ , _ , _ ] 插入5： [ 5, _ , _ , _ , _ , _ , _ , _ ] 插入2： [ 2, 5, _ , _ , _ , _ , _ , _ ]（二分查找确定位置在5前面） 插入8： [ 2, 5, 8, _ , _ , _ , _ , _ ] 插入1： [ 1, 2, 5, 8, _ , _ , _ , _ ] 复杂度分析： 时间复杂度：平均情况O(n log n)，最坏情况O(n²) 空间复杂度：O(n)的额外空间 优势：相比传统插入排序，减少了元素移动次数 优化策略： 动态调整空位密度：根据插入频率调整空位数量 智能重新平衡：只在必要时执行重新平衡操作 缓存友好的内存访问模式