-3

我对 BubbleSort 算法做了一些测试。我首先输入排序数组，然后是反向排序数组，然后是随机排序数组。我为 10000、100000 和 1000000 输入大小运行代码

以下是 1000000 输入大小的结果：

Sorted array: Actual running time = 304618 ms.
Reversely sorted array: Actual running time = 742047 ms.
Randomly sorted array: Actual running time = 1375477 ms.

代码 ：

void BubbleSort (int A[], int size)
{
int i, j;
for (i=0; i<n-1; i++)
    for (j=n-1; j>i; j--)
        if (A[j]<A[j-1])
            swap (A[j], A[j-1]);
}

为什么随机排序的数据比反向排序的数据花费更多时间？？？

4

1 回答 1

3

我将冒险猜测并说这是因为您编写算法的方式正在利用您的 CPU 分支预测。本质上，当您在反向数据上运行它时，几乎总是必须交换它，直到它处于正确的位置，而对于随机数据，情况不一定如此。你的 CPU 在做可预测的事情时会变得更快，而在做不可预测的事情时会变慢。随机数据是不可预测的。

有关更好的解释，请参见此处：https ://stackoverflow.com/a/11227902/1178052

于 2013-11-09T09:40:49.690 回答