返回工具主页

合并两个有序数组

从两个数组的末尾开始，使用 i、j、k 三个指针。每次挑选两个指针所指元素中较小的一个，写入合并数组当前末尾位置 k，然后 k 向左移动，最终得到完整的降序数组。

本演示假设两个输入数组均为降序排列，合并结果也为降序。

输入数组

合并过程可视化

数组1 数组2 合并数组
数组 1
数组 2
合并数组
点击“开始合并”启动演示。

操作控制

400ms
0
比较次数
0
写入次数

核心代码

def merge_sorted_lists(lst1, lst2):
total_length = len(lst1) + len(lst2)
merged_array = [0] * total_length
i, j = len(lst1) - 1, len(lst2) - 1
k = total_length - 1
while i >= 0 and j >= 0:
if lst1[i] < lst2[j]:
merged_array[k] = lst1[i]
i -= 1
else:
merged_array[k] = lst2[j]
j -= 1
k -= 1
while i >= 0:
merged_array[k] = lst1[i]
i -= 1
k -= 1
while j >= 0:
merged_array[k] = lst2[j]
j -= 1
k -= 1
return merged_array

三个指针均从末尾出发。i 和 j 指向两个待合并数组的当前元素，k 指向合并数组的写入位置。由于 lst1[i] < lst2[j] 时 lst1[i] 更小，因此把它先放到当前最靠后的空位 merged_array[k]；否则放 lst2[j]。较大的元素会留到下一轮写入更靠前的位置，因此从后往前填充后，最终得到降序结果。