老师，我写了一个希尔排序，用长度为150万的随机数组测试了一下，为什么比最初版本的快速排序速度还要快很多。

首页课程实战体系课手记专栏慕课教程

老师，我写了一个希尔排序，用长度为150万的随机数组测试了一下，为什么比最初版本的快速排序速度还要快很多。

来源：

mm隔心忘年

2017-01-11

/*用希尔排序算法对一随机数组排序*/
template<typename T>
void shellSort(T *arr, int n)
{

    for (int gap = n / 2; gap > 0; gap /= 2)

        for (int i = gap; i < n; i++) {

            T e = arr[gap];
            int j(i);
            for (int j = i; j > i && e < arr[j]; j -= gap)
                arr[j] = arr[j-gap];
            arr[j] = e;
        }

    for (int i = 1; i < n; i++) {

        T e = arr[i];
        int j(0);
        for (j = i; j > 0 && e < arr[j-1]; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }
}

而且如果是500万个随机数差的更大

吓到我了。。。

写回答

2回答

liuyubobobo

liuyubobobo

2017-01-11

如果是使用VS编译器的话，请确保测试性能是在release模式下运行的哦。不然性能测试的结果非常不准确。具体可以看这个问题：http://coding.imooc.com/learn/questiondetail/3603.html

0

3

mm隔心忘年

回复

liuyubobobo

自己写了swap；在release模式下还是差10倍左右

2017-01-11

共3条回复

mm隔心忘年

mm隔心忘年

提问者

2017-01-11

//szimg.mukewang.com/5875f2ce00014f3009380569.jpg

重新做的测试

0

2

mm隔心忘年

回复

liuyubobobo

OK！谢谢老师

2017-01-11

共2条回复

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

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

11187 学习 · 1614 问题

相似问题

为什么在我的电脑上运行快速排序要比归并排序要慢啊= =

回答 7

老师我不明白希尔排序为什么能那么快

回答 1

快速排序的划分

回答 3

我发现课程的双路快排和三路快排有区别

回答 2

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

回答 2

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