第2章 算法为何重要

上一章我们明白了选择合适的数据结构将会显著地提升代码的性能。在本章，你将会发现，就算数据结构确定了，代码的速度也还会受另一重要因素影响，那就是算法。

在计算机的世界里，算法是指某项操作的过程。一种操作可能会有不止一种做法。也就是说，一种操作会有多种算法的实现，不同的算法能使代码变快或者变慢——高负载时甚至慢到停止工作。

2.1 有序数组

有序数组跟数组几乎一样，唯一区别就是有序数组要求其值总是保持有序。即每次插入新值时，它会被插入到适当的位置，使整个数组的值仍然按顺序排列。

往有序数组中插入新值，需要先做一次查找以确定插入的位置。这是它跟常规数组的关键区别（在性能方面）之一。虽然插入的性能比不上常规数组，但在查找方面，有序数组却有着特殊优势。

2.2 查找有序数组

上一章介绍了常规数组的查找方式：从左至右，逐个格子检查，直至找到。这种方式称为线性查找。

有序数组的线性查找大多数情况下都会快于常规数组，因为对于有序数组来说，即便它不包含要找的值，我们也可以提早停止查找，除非要找的值是最后那个，或者比最后的值还大，那就只能一直查到最后了。

有序数组相比常规数组的一大优势就是它可以使用另一种查找算法。此种算法名为二分查找，它比线性查找要快得多。

2.3 二分查找

有序数组相比常规数组的一大优势就是它除了可以用线性查找，还可以用二分查找。常规数组因为无序，所以不可能运用二分查找。

用二分查找来找出7，过程如下。

第1步：检查正中间的格子。因为数组的长度是已知的，将长度除以2，我们就可以跳到确切的内存地址上，然后检查其值。

值为9，可推测出7应该在其左边的某个格子里。而且，这下我们也排除了一半的格子，即9右边的那些（以及9本身）。

第2步：检查9左边的那些格子的最中间那个。因为这里最中间有两个，我们就随便挑了左边的。

它的值为4，那么7就在它的右边了。由此4左边的格子也就排除了。

第3步：还剩两个格子里可能有7。我们随便挑个左边的。

第4步：就剩一个了。（如果还没有，那就说明这个有序数组里真的没有7。）

终于找到7了，总共4步。

2.4 二分查找与线性查找

对于长度太小的有序数组，二分查找并不比线性查找好多少。但对于拥有100个值的数组来说，线性查找最多需要100步，二分查找最多需要7步。再增大到1000000个元素，则线性查找最多有1000000步，二分查找最多只有20步。

元素有多少，线性查找的最多步数就是多少。数组长度翻倍，线性查找的最多步数就会翻倍，而二分查找则只是增加1步。

不过，有序数组并不是所有操作都比常规数组要快，它的插入就相对要慢。衡量起来，虽然插入是慢了一些，但查找却快了许多，我们需要根据应用场景来判断哪种更合适。

2.5 总结

很多时候，计算一样东西并不只有一种方法，换种算法可能会极大地影响程序的性能，世界上并没有哪种适用于所有场景的数据结构或者算法。不能因为有序数组能使用二分查找就永远只用有序数组。在经常插入而很少查找的情况下，显然插入迅速的常规数组会是更好的选择。如之前所述，比较算法的方式就是比较各自的步数。