2.1 有序数组

有序数组跟上一章讨论的数组几乎一样，唯一区别就是有序数组要求其值总是保持有序（你猜对了）。即每次插入新值时，它会被插入到适当的位置，使整个数组的值仍然按顺序排列。常规的数组则并不考虑是否有序，直接把值加到末尾也没问题。

以数组[3,17,80,202]为例。

假设这是个常规的数组，你准备将75插入，那就可以把它放到尾端，如下所示。

如上一章所述，计算机只要1步就能完成这种操作。

但如果这是一个有序数组，你就必须要找到一个适当的位置，使插入75之后整个数组依然有序。

做起来可不像说的那么简单。整个过程不可能一步完成，因为计算机需要先找出那个适当的位置，然后将其及以后的值右移来腾出空间给75。下面就来介绍分解的步骤。

先回顾一下原始的数组。

第1步：检查索引0的值，看75应该在它的左边还是右边。

因为75大于3，所以75应该在它右边的某个位置。而具体的位置，目前还是不能确定，于是，再检查下一个格子。

第2步：检查下一格的值。

因为75大于17，所以继续。

第3步：检查下一格的值。

这次是80，大于75。因为这是第一次遇到大于75的值，可想而知，必须把75放在80的左侧以使整个数组维持有序。但要在这里插入75，还得先将它的位置空出来。

第4步：将最后一个值右移。

第5步：将倒数第二个值右移。

第6步：终于可以把75插入到正确的位置上了。

可以看到，往有序数组中插入新值，需要先做一次查找以确定插入的位置。这是它跟常规数组的关键区别（在性能方面）之一。

虽然插入的性能比不上常规数组，但在查找方面，有序数组却有着特殊优势。