2.1 數組合并

在第1章中，我們了解了列表的使用方法。通過列表，可以建立內部只存在整型變量的數組?？梢杂脭到M來模擬指針。

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的數，就可以有效避免這個問題。

這樣，就使用模擬指針完成了兩個有序數組的合并。