图书馆排序（Library Sort）的插入优化策略与间隙维护机制

题目描述：
图书馆排序是一种改进的插入排序算法，通过在数组中预留间隙来减少元素移动次数。请实现该算法，并详细解释其间隙维护机制。

解题过程：

1. 基本思想
   图书馆排序的核心思想是在数组中预留一些空位（间隙），这样在插入新元素时，可以通过移动间隙而不是移动所有元素来减少数据移动次数。

2. 算法步骤

步骤1：初始化

• 创建一个大小为(1+ε)n的数组，其中n是待排序元素数量，ε是扩展因子（通常取0.5-1.0）
• 将数组初始化为包含间隙和元素的混合结构

def library_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    
    # 计算扩展后的大小，ε取0.5
    expanded_size = int(n * 1.5)
    expanded_arr = [None] * expanded_size  # None表示间隙
    
    # 初始放置：每隔一个位置放一个元素
    for i in range(n):
        expanded_arr[2*i] = arr[i]
    
    return _library_sort_main(expanded_arr, n, expanded_size)

步骤2：重新平衡操作
当间隙不足时需要重新平衡数组：

def _rebalance(arr, current_size, total_size):
    """重新平衡数组，重新分配间隙"""
    new_arr = [None] * total_size
    
    # 计算新的间隔，确保有足够间隙
    gap = total_size // (current_size + 1)
    j = 0
    
    for i in range(current_size):
        # 找到下一个非空位置
        while j < total_size and new_arr[j] is not None:
            j += 1
        
        # 移动元素到新位置
        if j < total_size:
            new_arr[j] = arr[i]
            j += gap
    
    return new_arr

步骤3：二分查找插入位置
由于数组中有间隙，需要找到正确的插入位置：

def _binary_search_with_gaps(arr, target, left, right):
    """在包含间隙的数组中进行二分查找"""
    while left <= right:
        mid = (left + right) // 2
        
        # 找到中间位置最近的元素
        mid_left = mid
        while mid_left >= left and arr[mid_left] is None:
            mid_left -= 1
        
        if mid_left < left:
            # 左边全是间隙，往右找
            mid_right = mid
            while mid_right <= right and arr[mid_right] is None:
                mid_right += 1
            
            if mid_right > right:
                return left
            elif arr[mid_right] >= target:
                return left
            else:
                left = mid_right + 1
                continue
        
        # 比较找到的元素
        if arr[mid_left] == target:
            return mid_left
        elif arr[mid_left] < target:
            left = mid_left + 1
        else:
            right = mid_left - 1
    
    return left

步骤4：主排序算法
结合以上组件实现完整的图书馆排序：

def _library_sort_main(expanded_arr, n, expanded_size):
    """图书馆排序主算法"""
    sorted_count = 1  # 已排序元素数量
    
    for i in range(1, n):
        # 检查是否需要重新平衡
        if _need_rebalance(expanded_arr, sorted_count, expanded_size):
            expanded_arr = _rebalance(expanded_arr, sorted_count, expanded_size)
        
        # 在已排序部分找到插入位置
        insert_pos = _binary_search_with_gaps(expanded_arr, 
                                            expanded_arr[2*i], 0, 2*(sorted_count-1))
        
        # 执行插入
        _insert_with_shift(expanded_arr, 2*i, insert_pos, expanded_size)
        sorted_count += 1
    
    # 移除间隙，返回结果
    return [x for x in expanded_arr if x is not None]

def _need_rebalance(arr, sorted_count, total_size):
    """检查是否需要重新平衡"""
    gap_count = 0
    for i in range(2 * sorted_count):
        if arr[i] is None:
            gap_count += 1
    
    # 如果间隙比例低于25%，需要重新平衡
    return gap_count / (2 * sorted_count) < 0.25

def _insert_with_shift(arr, source_idx, target_idx, total_size):
    """移动元素并插入"""
    if source_idx == target_idx:
        return
    
    element = arr[source_idx]
    arr[source_idx] = None
    
    # 确定移动方向
    if source_idx > target_idx:
        # 向右移动元素，为插入腾出空间
        for i in range(source_idx, target_idx, -1):
            arr[i] = arr[i-1]
    else:
        # 向左移动元素
        for i in range(source_idx, target_idx):
            arr[i] = arr[i+1]
    
    arr[target_idx] = element

3. 复杂度分析

时间复杂度：

• 最好情况：O(n log n) - 每次插入都是二分查找
• 平均情况：O(n log n)
• 最坏情况：O(n²) - 频繁重新平衡时

空间复杂度：O(n) - 由于需要额外的间隙空间

4. 优化策略

策略1：动态调整间隙密度
根据插入频率动态调整间隙密度：

def _dynamic_gap_management(arr, current_size, total_size, insert_frequency):
    """动态调整间隙密度"""
    if insert_frequency > 0.1:  # 高频插入
        new_size = int(total_size * 1.2)
    else:  # 低频插入
        new_size = int(total_size * 1.05)
    
    return _rebalance(arr, current_size, new_size)

策略2：批量插入优化
对多个元素进行批量插入，减少重新平衡次数：

def _batch_insert(expanded_arr, elements, start_idx, expanded_size):
    """批量插入多个元素"""
    # 先找到所有元素的插入位置
    insert_positions = []
    for elem in elements:
        pos = _binary_search_with_gaps(expanded_arr, elem, 0, len(expanded_arr)-1)
        insert_positions.append(pos)
    
    # 批量移动和插入
    # ... 具体实现省略

5. 实际应用示例

# 测试示例
def test_library_sort():
    arr = [5, 2, 8, 1, 9, 3, 7, 4, 6]
    print("原始数组:", arr)
    
    sorted_arr = library_sort(arr)
    print("排序后:", sorted_arr)
    
    # 验证结果
    assert sorted_arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print("测试通过!")

# 运行测试
test_library_sort()

图书馆排序通过巧妙的间隙管理机制，在保持插入排序简单性的同时，显著减少了元素移动次数，特别适用于部分有序或需要频繁插入的场景。