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步。

虽然有序数组的插入比传统数组慢，但其查找则另有玄机。