2.1　有序數組

有序數組和第1章中的“傳統”數組幾乎完全一致。你也能猜到，它們唯一的區別在于有序數組中的值是按順序排列的。也就是說，插入新值時，這個值必須被放到一個合適的格子中，以免打亂數組的順序。

以數組[3, 17, 80, 202]為例，如下圖所示。

假設要插入值75。如果這是一個傳統數組，那么可以像下圖這樣在末尾插入75。

如第1章所述，這只需要1步。

但如果這是有序數組，那么別無選擇，只能把75插入合適的位置，以保證數組的值是遞增的，如下圖所示。

這說起來容易，做起來難。計算機無法一步到位，把75放進合適的格子。這是因為它必須先找到合適的格子，再移動其他值來騰出空間。下面來一步步分析這個過程。

首先是原來的有序數組，如下圖所示。

第1步：檢查索引0處的值來確定要在它前面還是后面插入新值75，如下圖所示。

因為75比3大，所以必須插到它右邊。不過，因為依然不知道具體位置，所以必須檢查下一個格子。

這樣的步驟叫作比較。我們會比較要插入的值和有序數組中現有的值。

第2步：檢查下一個格子的值，如下圖所示。

75比17大，所以還得繼續右移。

第3步：檢查下一個格子的值，如下圖所示。

這次的值是80，比要插入的75大。因為我們碰到了第一個比75大的值，所以得出結論：要保證有序數組的有序性，75必須緊挨著放在80的左邊。為此，需要右移數據為75騰出空間。

第4步：把最后一個值右移，如下圖所示。

第5步：把倒數第二個值右移，如下圖所示。

第6步：把75插到正確的位置，如下圖所示。

可以看出，當向有序數組插入元素時，總是需要在插入前查找正確的插入位置。這就是傳統數組和有序數組在性能上的差別之一。

在這個例子中，數組有4個元素，插入用了6步。而對于包含N個元素的有序數組，插入則需要花N+2步。

有趣的是，在有序數組中，無論新值最后插到哪里，所需的步驟數都差不多。如果這個值最后位于數組開頭，那么所需的比較就更少，移動就更多。如果它最后位于數組末尾，那么比較就更多，移動就更少。當新值位于數組的最末尾時，因為不需要移動任何數據，所以總共需要的步驟數就最少。在此情況下，和N個現有的值比較需要N步，而插入本身還需要1步，因此，共計為N+1步。

雖然有序數組的插入比傳統數組慢，但其查找則另有玄機。