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

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#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：很多改进不是普遍意义的改进，而是针对某一类特殊数据情况的改进，我们在后面会经常讨论这些情况，比如对近乎有序的数组；或者有很多重复元素的数组。测试这些特殊情况的优化结果。