同样一个数组(拷贝的数组)两次排序，所用的时间为什么会不一样呢？(好像冒泡排序的优化，跟插入排序有些相似呢）

Question

#include "SortTestHelper.h"
int main(void)
{
    void BubbleSort(int* arr ,int n);
    void BubbleSortAdvance(int* arr,int n);
    int n = 100000;
    int *arr = SortTestHelper::generateRandom(n,1,100000);
    int *arr1 = SortTestHelper::copyIntArray(arr,n);
    int *arr2 = SortTestHelper::copyIntArray(arr,n);
    SortTestHelper::testSort("BubbleSort",BubbleSort, arr,n);
    SortTestHelper::testSort("BubbleSort",BubbleSort,arr1,n);
    SortTestHelper::testSort("BubbleSortAdvance",BubbleSortAdvance,arr2,n);
    return 0;
}
void BubbleSort(int* arr,int n)
{
    for(int i = 0;i < n;i++)
    {
        for(int j = 1;j < n - i;j++)
        {
            if(arr[j - 1] > arr[j])
                swap(arr[j - 1],arr[j]);
        }
    }
}
void BubbleSortAdvance(int* arr,int n)
{
    for(int i = 0;i < n;i++)
    {
        int j = 0;
        int temp = arr[j];
        for(int j = 0;j < n - i - 1;j++)
        {
            if(temp > arr[j + 1])
            {
               // temp =  arr[j];
                arr[j] = arr[j+1];
            }
            else
            {
                arr[j] = temp;
                temp = arr[j + 1];
            }
            arr[j + 1] = temp;
        }
    }
}

BubbleSort : 36.466s
BubbleSort : 36.384s
BubbleSortAdvance : 30.072s

Answer 1

liuyubobobo 2017-01-16 10:30:09

程序在我们的计算机上运行的时候，除了我们自己的程序本身的算法性能外，计算机当时的状态，如后台正在运行的程序等，都会影响程序的执行速度。所以，近乎不可能每次执行程序运行的时间是一样的：）

• 提问者 MrJean #1

  原来是这样，谢谢波波老师~

• 提问者 MrJean #2

  还有一个疑问，自己下来写了一个冒泡的改进算法。和原来的算法对比，程序运行的时间只快一点点。因为程序近乎每次运行的时间不可能一样。我是否应该认为改进的算法没有达到优化的效果呢？应该怎样鉴别算法是否优化？

• liuyubobobo 回复 提问者 MrJean #3

  方法1：扩大程序运行的数据规模，适用于复杂度级别的改进。很多改进算法，在n=100的情况下看不出效果，但是n=10000就不一样了，n=1000000甚至就变成了可以接受和不可以接受的差距；方法2：多次运行取平均值，这样均衡掉偶然的计算机本身的状态产生的误差，用统计结果说话而不是单次运行结果，更有说服力；方法3：很多改进不是普遍意义的改进，而是针对某一类特殊数据情况的改进，我们在后面会经常讨论这些情况，比如对近乎有序的数组；或者有很多重复元素的数组。测试这些特殊情况的优化结果。