Python实现数组合并

在算法中,指针的概念常常被应用。比如说二分查找中存储查找范围最左和最右元素的两个变量,就可以理解为左指针和右指针,因为它们起到了“存储数据储存位置”的作用。

在 Python 中,标准意义上的指针并不存在。不过,Python 语言的许多内置函数和功能都使用了指针来编写——比如说列表,实际上是以链表的形式存在的。不过,程序员无法在用 Python 编写程序的时候直接使用真正意义上的指针;所以,本节教程会以模拟指针的形式在 Python 中传达指针的概念。

编写程序时,我们可以通过下标来找出某个值。存储下标值的变量可以被看作一个指针。我们可以以这个概念来实现 Python 中的指针问题。这种问题称为“模拟指针问题”,因为它用到了指针的思想,但没有用到真正意义上的指针。

数组合并问题是一个典型使用了指针思想的问题:有两个从小到大有序排列的数组,如图 1 所示。
两个有序数组
图 1:两个有序数组

有两个长度为 5 的有序数组。使用指针的思想,就可以把它们合并成一个从小到大排列的数组。

先用图来演示合并数组的过程。

1) 第一步:如图 2 所示,拿出第二个数组的第一个元素,把它和第一个数组的第一个元素进行比较。
第一次比较
图 2:第一次比较

2 小于第一个元素 3,此时把 2 放入一个空列表的第一位,如图 3 所示。
把元素加入结果列表中
图 3:把元素加入结果列表中

2) 第二步:完成第一步后,第二个列表的指针向后一位,指向第二个元素 4。再把两个指针指向的元素比较,3小于4,这时把3加入结果列表中,如图 4 所示。
向第一个数组中插入2
图 4:向第一个数组中插入2

3) 第三步:相似地,不断重复比较两个指针指向的元素并把它们加入结果列表,以图 5 为例。
重复以上步骤
图 5:重复以上步骤

4) 第四步:如图 6 所示,两个列表中都只剩下一个元素。这时候,第二个列表中的元素 14 比较小。把元素 14 加入结果数组。
倒数第二步
图 6:倒数第二步

如图 7 所示,此时,已经有一个列表全部加入了结果列表,所以另一个列表中的元素可以直接全部按顺序加入列表的最后几位。
准备插入第二个元素
图 7:准备插入第二个元素
 
数组就合并成图 8 所示的样子了。
排序完成
图 8:排序完成

再把这个过程转化为程序:
arr1 = [3,6,9,12,15]          #初始化两个数组
arr2 = [2,4,7,13,14]
i,j = 0,0               #指针初始化,指向列表第一个数
ans = []                #ans初始化为空
while i < len(arr1) and j < len(arr2): #当有一个指针不再指向元素时停止循环
    if arr1[i] <= arr2[j]:       #判断大小,把元素加入结果列表,挪动指针
        ans.append(arr1[i])
        i += 1
    else:
        ans.append(arr2[j])
        j += 1
if i == len(arr1):           #把还有剩余长度的列表中的元素加入结果列表
    ans += arr2[j:]
else:
    ans += arr1[i:]
print(ans)
这样,就使用模拟指针完成了两个有序数组的合并