近似有序，归并一直比双路快排快很多

Question

测试近似有序的数据，归并一直比快排2快了一个数量级，而且随着 swapTimes 的增加，时间也没有太大的变化，对比其他的测试结果（随机和等值都正常，只有近似有序快的不正常），又似乎不是代码的问题。Windows VS Release 调试

Answer 1

liuyubobobo 2018-03-21 09:29:29

如果快排添加了随机化的操作，不应该和归并有这么大的差距。使用课程github上的官方代码，看看是否也是这样的？https://github.com/liuyubobobo/Play-with-Algorithms

• 提问者 SunYizhi #1

  嗯，试过了，结果差不多，应该还是 VS 调试设置的有问题，这个软件功能太强了，不大会用 @_@ 。本地调试结果：
  Test for nearly ordered array, size = 1000000, swap time = 100
  Merge Sort : 0.007 s
  Quick Sort : 0.136 s
  网上找了两款在线调试器，结果果然不同了：
  Test for nearly ordered array, size = 1000000, swap time = 100
  Merge Sort : 0.1 s
  Quick Sort : 0.04 s
  以及：
  Test for nearly ordered array, size = 1000000, swap time = 100
  Merge Sort : 0.075031 s
  Quick Sort : 0.084559 s

• liuyubobobo 回复 提问者 SunYizhi #2

  @_@ 这样啊。听说Windows平台，VS Code是非常好的IDE，也比VS轻量得多。不过听说而已，我没有实际使用过，有时间我测试一下看看。VS最大的问题是C++编译器是微软自己的实现，而不是标准实现，使得一些语法和国际标准不兼容。不过听说最新的版本(VS 2017)越来越好：）

• 提问者 SunYizhi 回复 liuyubobobo #3

  嗯嗯，谢谢老师