原地（in-place）排序两个已排序数组：将前n小元素存入首数组

问题描述 #

给定两个长度分别为n和m的升序整数数组，需完成：

• 将所有元素中最小的n个存入第一个数组
• 剩余元素存入第二个数组
• 算法必须**原地（in-place）**实现
• 时间复杂度不得超过O(m·n)

输入输出规则：

• 输入：第一行输入n和m；后续两行分别为两个数组的元素（0≤n,m≤1000）
• 输出：分别打印处理后的两个有序数组，第一行是第一个数组，第二行是第二个数组

当前实现问题 #

目前采用归并排序思路，合并两个数组后排序再拆分，但该方案需要额外空间存储合并后的数组，不符合原地实现要求，需寻找原地解法。

现有代码 #

def merge_sort(array):
    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left_half = array[:mid]
    right_half = array[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1

    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1

    return merged

def store_nsmallest_elements(array1, array2, n, m):
    sorted_array = merge_sort(array1 + array2)
    return sorted_array[:n], sorted_array[n:n+m]

n, m = map(int, input().split())
array1 = list(map(int, input().split()))
array2 = list(map(int, input().split()))

first, second = store_nsmallest_elements(array1, array2, n, m)

print(*first)
print(*second)

原地解法思路 #

利用两个数组本身的升序特性，结合原地交换+插入排序实现，步骤如下：

1. 交叉交换调整

   • 用指针i指向数组1的末尾（初始值n-1），指针j指向数组2的开头（初始值0）
   • 循环比较array1[i]和array2[j]：
     • 若array1[i] > array2[j]，交换两者（把数组1里的大元素换到数组2，数组2的小元素换到数组1）
     • 交换后i -= 1，j += 1，直到i < 0或j >= m时停止
   • 这一步的目的是让数组1尽可能保留小元素，数组2保留大元素，利用了两个数组的有序性，时间复杂度O(min(n,m))

2. 原地排序整理

   • 经过交换后，两个数组内部可能不再有序，分别对数组1和数组2执行插入排序
   • 插入排序是原地排序算法，时间复杂度O(k²)（k为数组长度），对于n和m最大1000的情况，O(n² + m²) ≤ O(mn)，符合题目时间要求

示例流程 #

比如数组1=[3,5,7]（n=3），数组2=[2,4,6]（m=3）：

• 交换7和2 → 数组1=[3,5,2]，数组2=[7,4,6]，i=1，j=1
• 交换5和4 → 数组1=[3,4,2]，数组2=[7,5,6]，i=0，j=2
• 3 < 6，停止交换
• 对数组1插入排序得到[2,3,4]，数组2插入排序得到[5,6,7]，完成目标

内容的提问来源于stack exchange，提问作者Phantom