原文來自
http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array?rq=1

首先有這樣一段簡單的程序：

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

原文說運行時間1.93s，我試了一下

排過序的運行時間

可能是CPU差距有點大吧。。

然后去掉排序那一句：
原文是11.54s

未排序

原文作者用JAVA也試了，但是時間差距沒C++這么大。

為什么處理排過序的數(shù)組更快呢？

我要開始搬運了，純屬意譯，不準(zhǔn)確的請指出：）

假如你在這個岔道口給火車指向

如果有一個鐵路分叉口，你在那里給鐵路指向，但是你不知道火車要去的地方在哪個方向，你只能猜啊，如果你猜對了火車就順利跑過去了，但是如果你猜錯了，你要知道，火車質(zhì)量那么大，啟動和停下來都很耗時間！
So they take forever to start up and slow down(哈哈，forever)

再來看計算機：

if (data[c] >= 128)
sum += data[c];

計算機運行到這一步怎么辦啊，它哪里知道是不是該執(zhí)行這一句??！它得停下來執(zhí)行這個判斷語句了才知道。判斷完成了你才能繼續(xù)之前的計算。

然而現(xiàn)代的計算機處理器都使用的是流水線技術(shù)，（把復(fù)雜的運算分成一步一步，增加處理效率）
Modern processors are complicated and have long pipelines. So they take forever to "warm up" and "slow down".
和火車一樣你讓快速運行并且復(fù)雜的流水線停下來是非常耗時間的事情。

（這里我猜測一下是不是會在判斷的時候預(yù)執(zhí)行一條分支？）

所以電腦也靠猜，猜對了就很流暢，但是猜錯了也是非常耗時間的。

所以就是怎么樣猜的更準(zhǔn)了，電腦會試圖找到一條規(guī)律。

Most applications have well-behaved branches. So modern branch predictors will typically achieve >90% hit rates. But when faced with unpredictable branches with no recognizable patterns, branch predictors are virtually useless.

也就是說電腦會根據(jù)之前的結(jié)果，選擇概率更大的，如果之前有很多都是往右的，電腦會猜測下一次也往右。

wiki上Branch predictor的解釋

如果是排過序的，那么規(guī)律很明顯，電腦判斷成功的幾率就高很多

排序之后的分支走向

未經(jīng)排序的數(shù)據(jù)很亂，判斷成功的幾率很低：

未排序的分支

So what can be done?
If the compiler isn't able to optimize the branch into a conditional move, you can try some hacks if you are willing to sacrifice readability for performance.
Replace:
if (data[c] >= 128) sum += data[c];
with:
int t = (data[c] - 128) >> 31; sum += ~t & data[c];
This eliminates the branch and replaces it with some bitwise operations.
(Note that this hack is not strictly equivalent to the original if-statement. But in this case, it's valid for all the input values of data[]
.)

最高贊回答者這樣替換了一下代碼，這樣看起來多了一些運算。