一文深入详解为什么有序数组比无序数组快

当我们讨论数组操作的性能差异时，“有序数组比无序数组快”是一个很容易被感知到的结论：同样是查找一个元素，有序数组可能几毫秒就能返回结果，无序数组却要花上几十倍的时间;同样是做数据统计，有序数组的计算速度往往远超随机排列的数组。这个差异背后，本质是数据的有序性降低了操作的时间复杂度，让计算机可以用更高效的逻辑处理数据。

查找操作：从遍历到二分的效率跃迁

查找是数组最常见的操作，也是有序数组和无序数组性能差距最明显的场景。对于无序数组来说，查找一个元素只能用线性遍历的方法：从数组的第一个元素开始，逐个和目标值对比，直到找到匹配的元素，或者遍历完整个数组确认不存在。这种方法的平均时间复杂度是O(n)，也就是说数组里有1000个元素，平均就要查找500次;如果有100万个元素，平均就要查找50万次，数据量越大，效率越低。

而有序数组可以使用二分查找法，利用数据的有序性不断缩小查找范围。比如要在一个升序排列的数组里找目标值，只需要先对比数组中间的元素：如果中间元素等于目标值，直接返回结果;如果中间元素比目标值大，说明目标值只可能存在于数组的左半部分，直接把右半部分舍弃;如果中间元素比目标值小，就舍弃左半部分。每次对比都能把查找范围缩小一半，时间复杂度只有O(log n)。

这个效率差距在数据量越大的时候越夸张。比如数组长度是100万，无序数组的平均查找次数是50万次，而有序数组的二分查找最多只需要20次(2的20次方是1048576)，速度差了2.5万倍。如果是千万级别的数据，无序数组查找一次要遍历几百万次，有序数组依然只需要24次左右，差距达到了几十万倍。这也是为什么数据库的索引都会用有序结构存储，核心就是利用有序性把查找操作的复杂度降下来。

哪怕不是精确查找，只是范围查找，有序数组的优势同样明显。比如要找数组里所有大于100小于200的元素，无序数组必须遍历所有元素逐一判断，而有序数组只需要用二分查找找到第一个大于100的元素，再找到第一个大于200的元素，中间的所有元素都符合要求，不需要再逐个对比，操作效率提升了几个量级。

统计与计算：利用有序性避免重复操作

除了查找之外，很多常见的数组统计操作，有序数组都能凭借数据的排列规则大幅降低比如最常见的去重操作，无序数组需要额外用一个哈希表存储已经出现过的元素，遍历每个元素的时候都要查询哈希表判断是否重复，不仅时间复杂度是O(n)，还要占用额外的O(n)存储空间。而有序数组里重复的元素必然是相邻的，只需要一次遍历，对比当前元素和前一个元素是否相等就能完成去重，不需要额外的存储空间，操作速度比无序数组快30%以上，还不会有哈希冲突的额外开销。

再比如求众数、中位数、Top K元素这类统计场景，有序数组可以直接得出结果。求中位数只需要取数组中间位置的元素，时间复杂度O(1)，而无序数组需要先排序或者用堆结构计算，时间复杂度至少是O(n log n)。求Top 10最大的元素，有序数组直接取最后10个元素就行，无序数组要么遍历所有元素维护一个小顶堆，要么排序后再取，计算量要大得多。

还有交集、并集这类多数组操作，有序数组的优势更加明显。比如计算两个数组的交集，无序数组需要把其中一个数组的元素存入哈希表，再遍历另一个数组查询，同样有额外的空间开销，而有序数组只需要用双指针法：两个指针分别指向两个数组的起始位置，每次对比指针指向的元素，如果相等就是交集元素，两个指针同时后移;如果不等，就把指向较小元素的指针后移。整个过程不需要额外空间，速度比哈希表法快一倍以上，数据量越大优势越明显。

底层硬件：有序性带来的缓存友好性

很多人忽略的一点是，有序数组的操作速度更快，还有硬件层面的原因。现代CPU都有缓存预取机制，当访问数组中的一个元素时，CPU会把相邻的几个元素也提前加载到缓存里，因为程序通常会访问相邻的数据，这就是“空间局部性”原理。有序数组的操作大多是顺序或者按固定步长访问，比如二分查找虽然是跳着访问，但每次跳转的步长是不断缩小的，依然符合空间局部性的规律，缓存命中率很高，访问内存的延迟很低。

而无序数组的很多操作都是随机访问，比如用哈希表去重的时候，访问哈希表的地址是随机的，缓存命中率很低，每次访问都要从主存里读取数据，而主存的访问延迟是CPU缓存的上百倍。即使是同样的遍历操作，无序数组如果在内存中是不连续存储的(比如动态扩容的链表结构数组)，缓存预取机制完全失效，访问速度会比有序数组慢很多。

还有分支预测的影响，CPU的分支预测器会预判程序下一步要执行的指令，如果预判正确，就能提前加载指令，提升执行速度。有序数组的条件判断往往有很强的规律性，比如二分查找的对比操作，在查找范围比较大的时候，大小关系的变化是有规律的，分支预测器很容易预判正确，而无序数组的元素是随机排列的，对比结果毫无规律，分支预测的失败率很高，每次预测失败都要清空流水线重新加载指令，也会拖慢执行速度。

注意：有序数组的优势是有前提的

当然，“有序数组更快”并不是绝对的，这个结论成立的前提是数组的查找、统计操作远多于插入、删除操作。因为要维持数组的有序性，插入和删除元素的时候需要移动大量元素，时间复杂度是O(n)，而无序数组的插入删除只需要O(1)的时间。如果你的业务场景是写多读少，频繁插入删除元素，那么维护数组有序的开销反而会超过有序性带来的收益，此时用无序数组反而更合适。

另外，对于很小的数组，比如长度只有10以内，有序数组和无序数组的性能差距几乎可以忽略，此时二分查找的逻辑开销甚至比直接遍历还要大。只有当数据量超过30个元素的时候，二分查找的优势才会逐渐体现出来。实际开发中需要根据业务场景选择合适的数据结构，不能盲目追求有序性。