一些排序问题

Question

我发现了一种方法可以改进(就我已经测试过的)快速排序算法,超出了已经完成的范围.我正在测试它,然后我想了解它.但是,我会感谢一些帮助.所以这是我的问题.顺便说一句,我的所有代码都是用C++编写的.

1. 我一直在与我的快速排序进行比较的一种方法是来自C++标准库的std :: sort.但是,它似乎非常缓慢.我只是排序整数和长期数组,但它似乎比我的快速排序和Bentley和McIlroy(也许是Sedgewick)的标准快速排序慢了大约8-10倍.有没有人有任何想法,为什么它这么慢？我用于排序的代码只是std :: sort(a,a + numelem); 其中a是long或int的数组,numelem是数组中元素的数量.数字是非常随机的,我尝试了不同的大小以及不同数量的重复元素.我也尝试过qsort,但是我的预期更糟糕了.编辑:忽略第一个问题 - 它已经解决了.

2. 我想找到更好的quicksort实现来与我的quicksort进行比较.到目前为止,我有一个Bentley-McIlroy,我还与Vladimir Yaroslavskiy的双枢轴快速排序的第一个版本进行了比较.另外,我计划移植timsort(我认为这是合并类型)和来自jdk 7源的优化双枢轴快速排序.你知道其他什么样的快速实施方案？如果他们不是C或C++,那可能没事,因为我非常擅长移植,但如果你知道它们我会更喜欢C或C++.

3. 你会如何推荐关于我对quicksort的补充？到目前为止,我的quicksort似乎比我测试过的所有其他quicksort快得多.它速度的主要来源是它比我发现的其他方法更有效地处理重复元素.它几乎完全消除了最坏情况的行为,而没有在检查重复元素上花费太多时间.我在Java论坛上发布了它,但没有得到回复.我还试着写信给Jon Bentley,因为他正在与弗拉基米尔合作进行他的双枢轴快速反应并没有得到任何回应(尽管我对此并不感到非常惊讶).我应该写一篇关于它的论文并把它放在arxiv上.ORG？我应该在一些论坛上发帖吗？我应该发布一些邮件列表吗？我已经在这方面工作了一段时间,我的方法是合法的.我确实有一些出版研究的经验,因为我是计算物理学的博士候选人.我应该尝试接触我大学计算机科学系的某个人吗？顺便说一句,我还开发了一个不同的双枢轴快速排序,但它并不比我的单枢轴快速排序更好(尽管它比弗拉基米尔的双枢轴快速排序更好,有一些数据集).

我非常感谢你的帮助.我只想将我能为计算机世界添加的内容.我对这种或任何荒谬的事情申请专利并不感兴趣.

Answer 1

如果您对自己的工作充满信心,请务必尽快与您所在大学的知识人士讨论.仅显示您的代码比计算机上的其他过程运行得更快是不够的.您必须在数学上证明您声称通过分析算法获得的性能提升.我要说的第一件事就是确保你所比较的两种算法都是以最佳方式实现和编译的 - 你可能只是在这里愚弄自己.在没有完全了解其可接受的变体的情况下,个体在这种重要的分类方法上实现这种显着改进的可能性似乎是微不足道的.但是,不要让我灰心.无论如何它应该是有趣的.你愿意在这里发布代码吗？...也,由于快速排序特别容易受到最坏情况的影响,因此您选择运行的测试可能会产生巨大影响,枢轴的选择也会产生巨大影响.一般来说,我会说任何具有大量等效元素的数据集或者已经高度排序的数据集对于快速排序来说永远不是一个好的选择 - 并且已经有众所周知的方法来对抗这种情况,以及更好的替代排序方法.

Answer 2

如果你真的取得了突破并有数学证明,你应该尝试将它发表在ACM期刊上.它绝对是最负盛名的计算机科学期刊之一.

第二好的是IEEE期刊之一,如 软件工程交易.