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

Question

/*用希尔排序算法对一随机数组排序*/
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万个随机数差的更大

吓到我了。。。

Answer 1

liuyubobobo 2017-01-11 16:24:04

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

• 提问者 mm隔心忘年 #1

  使用的code::blocks

• liuyubobobo 回复 提问者 mm隔心忘年 #2

  看看是不是也有debug或者release模式的区别？或者编译的时候可否加编译优化的参数。在一些情况下，希尔排序比快排快一些是有可能的，但差距这么大是有问题的。
  
  如果你的实现没有问题，我之前的经验是，在一些编译条件下，std::swap大大拖慢了快排的速度。试试看，自己写一个swap，很有可能都比调用std::swap快：）

• 提问者 mm隔心忘年 回复 liuyubobobo #3

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

Answer 2

提问者 mm隔心忘年 2017-01-11 16:55:03

重新做的测试

• liuyubobobo #1

  我晚上下载一个code::block试验一下。

• 提问者 mm隔心忘年 回复 liuyubobobo #2

  OK！  谢谢老师