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

Question

1.我发现课程里双路快排是双路遍历，并把数组分为两部分；三路快排是一路遍历，并把数组分为三部分，是不是这样的？那我能不能把三路快排改成双路遍历并把数组分为三部分？这样会增加逻辑语句，对性能会有什么影响？
2.老师您的电脑是什么cpu？我用三路快排排一百万个元素的数组竟然得三百多秒

Answer 1

liuyubobobo 2019-03-09 15:37:26

1

是这样。你可以使用你希望的方式更改逻辑，只要这个遍历过程是O(n)（当然逻辑也要正确），三路快排整体就是O(nlogn)的。不同的实现，可能会对性能有细微的影响，但是这些细微的影响（多一个if，少一个++一类的），不是我们学习算法讨论的重点。我们学习算法讨论的重点，在于不同复杂度级别之间的算法性能的巨大差异。再怎么优化选择排序，当数据规模增大的时候，它都不会比快速排序快。这是O(n^2)级别的算法和O(nlogn)级别的算法的本质差异。

2

我录课用的机器很老了。具体参数已经忘了，是一台13年的macbook air。一般近两年购买的机器，应该都比我的机器快。如果你的实现结果的慢的，请确定：

1）确认逻辑是正确的。可以下载课程的官方代码，在你的机器上运行作比较；

2）确认同样也是使用C++，不同语言，运行的性能差距是巨大的。比如使用Java，运行速度比C++慢是正常的，因为Java语言是运行在JVM上的。更不用提Python或者PHP一类的了；

3）如果使用VS，请使用release模式测试（或者其他IDE，使用release模式试试看）

加油！：）

• 提问者 脑子笨学不会 #1

  我是用golang写的，在其他算法上，golang性能和c++几乎没有差别，但就这次的快速排序算法，当数组元素超过十万，达到一百万数量级时候，就和c++产生了巨大差别

• liuyubobobo 回复 提问者 脑子笨学不会 #2

  抱歉，我对golang不是很熟悉，你需要在golang相关社群去讨论，在这种情况下是什么语言特性在影响性能，如何做fix。加油！：）

• 提问者 脑子笨学不会 回复 liuyubobobo #3

  好的，知道了。谢谢您！

点开查看后面1条评论

Answer 2

潇潇雨歇兮我材天生 2020-03-28 00:34:24

其实不是百万，从10万改成20万的时候就出问题了。网上也查不到这个错误代码具体是啥子玩意。。。

• 潇潇雨歇兮我材天生 #1

  自己调试了一个完全重复的元素的数组发现了问题所在：
  就是右索引变为 -1导致bug出现。当然了，这也是设计问题，因为自己使用的是无符号std::size_t 。。。而非int。。老师给的代码没有问题，是我自己细节设计出问题了。