快速带O的最坏的情况下（N log n）的

Question

我要实现快速排序，但带O的最坏情况（N log n）的。我可以实现文献中找到的任何东西，但到目前为止，我所能找到的就是名为BSort的东西，这对我来说没有什么意义。有没有人知道任何易于实现的算法的参考？或关于这个问题的文件？

是的，它是一流的，但是这一部分，我可以得到帮助，我只是要实现它在我自己的。

谢谢

Answer 1

有一个老问题，似乎是相同的：

Can we do Quick sort with n logn worst case complexity?

您是否已经就这一看一下吗？

Answer 2

这就是我发现的。我从来没有试图实现它或看alghoritm，但它说它有最坏的情况O（n日志n）。这是快速排序和堆排序

http://en.wikipedia.org/wiki/Introsort

我believee没有alghoritms即得到O（nlogn）最坏的情况下有简单的解决方案（快速排序的升级）的组合。

Answer 3

你的问题对我来说不是很清楚。

如果实现快速排序（例如，如所定义here），它会具有的O的最坏情况的运行时（N ** 2）。如果您正在实施“纯粹”Quicksort，则无法避免这种情况。

你想有一个O（N *的log（n））最坏的情况不同的排序算法，或者你想要一个优化的快速排序？

无论哪种方式，联系我给你会给你的算法的一些想法。

我从来没有听说过BSort的，你可以给一个链接？