2.1 数组合并

在第1章中，我们了解了列表的使用方法。通过列表，可以建立内部只存在整型变量的数组。可以用数组来模拟指针。

2.1.1 合并有序数组

指针的意思是内存空间的地址。可以通过一个数组中每个元素的下标来找出它的值，所以存储这个元素位置的下标值的变量可以看作一个指针。我们将以这个概念来实现Python中的指针问题。由于它不是真正意义上的指针，所以我们叫它“模拟指针问题”。

我们先来看第一个问题：数组合并问题。

有两个从小到大有序排列的数组，如图2.1所示。

第一个数组里有5个元素，第二个数组里有4个元素。要想把它们合并成一个新的从小到大排列的数组，该怎么编程实现呢？

在开始编写程序之前，我们先来了解一下这道题的思路。

首先拿出第二个数组的第一个元素2，把它和第一个数组中的第一个元素进行比较，如图2.2所示。

2比1要大，所以移动到第一个数组的第二个元素3，再次进行比较，如图2.3所示。

2比3要小，而我们已经知道2比前面的1要大，所以可以把2插到3的位置。3和它后面的元素都向后移动一个位置，如图2.4所示。

这时第二个数组中还剩下三个元素5、8、11。把5拿出来从3开始比较。注意，因为两个数组都是从小到大有序排列的，2在原来的第二个数组中排在5前面，所以它和它前面的数字都比5小，直接从3开始比较即可，如图2.5所示。

5在6这里停下，因为6大于5。把5插到6的前面，如图2.6所示。

完成插入后，第一个数组如图2.7所示。

随后，再重复之前的操作，直到第二个数组中的所有元素都被插入第一个数组中。此时排序完成，结果如图2.8所示。

现在来把这个过程转换为程序。

首先需要一个for循环对第二个数组arr2实现从小到大的遍历：

for i in range（0,len（arr2））:

随后在for循环内部加上while对arr1进行操作：

注意：Python中的数组也叫列表，为了方便理解统一称为数组。

其中，ind是存储数组中数值的下标的变量，ans用于存储排序完毕后的数组中的变量（初始值为arr1）。为什么不使用for循环而要用while呢？因为同一个数前面可能要插入两个数字，而for循环只能让它的前面插入一个数。

2.1.2 最终代码

用指针合并两个有序数组的程序如代码2.1所示。

代码2.1 用指针合并两个有序数组

其中，while...else语句是用来判断while循环是否被完整执行完的语句。如果while循环的结束是因为while后面的判断语句（ind < len（arr1））的返回值为False，则执行else；如果是因为break而跳出循环，则不执行else。

有人可能会有疑问：为什么要用ans存储arr1的值，而不在arr1内部直接改动呢？如果直接使用arr1存储答案，在向数组中添加元素的过程中，列表内部的元素会变化，也就是说，我们丢失了arr1的原来的值。用ind调用原来列表中的元素与arr2中的元素进行比较，而向ans中插入arr2的数，就可以有效避免这个问题。

这样，就使用模拟指针完成了两个有序数组的合并。