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

来源：

MrJean

2017-01-15

#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

写回答

1回答

liuyubobobo

2017-01-16

已采纳

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

liuyubobobo

MrJean

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

2017-01-16

共3条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11229 学习 · 1617 问题

查看课程

相似问题

对一个完全有序的数组，用插入排序进行优化，反而慢的不可思议

回答 1

优化后的冒泡排序似乎并没有体现出优势？

回答 1

归并排序求逆序数

回答 1

为何有递归的自顶向下的排序方法要快？

回答 2

为什么插入排序会远远由于归并排序？

回答 1

打开慕课网App查看更多内容