2回答

liuyubobobo

2019-03-09

已采纳

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模式试试看）

加油！：）

0

4

潇潇雨歇兮我材天生

回复

脑子笨学不会

三路快排我也觉得有些问题，可又找不出哪里有问题。 10万数据量正常，100万以上时，我的程序也出不来结果。。以为是内存爆了，重启机器还是无效。运行环境 VS2017，Release模式什么的都用了，找不出问题所在。 不过双路快排在1亿数据量（八个0）时都正常，三路待探究。

2020-03-28

共4条回复

潇潇雨歇兮我材天生

2020-03-28

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

0

1

潇潇雨歇兮我材天生

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

2020-03-28

共1条回复