速度排序的最佳算法是什么？

Question

有气泡，插入，选择，快速排序算法。

哪一个是“最快”的算法？

代码大小并不重要。

Bubble sort
insertion sort
quick sort

我试着检查速度。当数据已经被排序时，冒泡，插入的Big-O是n，但是算法在大列表上太慢了。

只使用一种算法好吗？或者更快地使用不同的混合？

Answer 1

快速排序通常是非常好的，只有当数据已经接近有序时，或者当数据具有很大的相似性(大量的键重复)时，才会真正下降，在这种情况下，它会变慢。

如果你对你的数据一无所知，而且你也不介意冒着快速排序的危险(如果你想一想，你可能会对你的情况做出判断-如果你有可能(从已经排序的数据中)得到这个)，那么快速排序就不会是一个糟糕的选择。

如果您决定您的数据有时或将要被排序(或经常是一个问题)已经排序(或明显地部分排序)，或以一种方式或另一种方式，您决定您不能冒险的最坏的情况下快速排序，然后考虑时间排序。

但是，正如对您的问题的评论所指出的，如果拥有最终的性能真的很重要，那么您应该考虑实现几种算法，并在有代表性的示例数据上尝试它们。

Answer 2

HP / Microsoft：：sort是内向 (在嵌套达到某种限制时，快速排序切换到堆排序)，而std::stable_sort是自下而上合并的一种变化。

对于排序数组或向量的大部分是随机整数，计数/基数排序通常是最快的。

大多数外部排序是k路自下而上合并排序的一些变化(初始内部排序阶段可以使用上述任何算法)。

为了排序一个小的(16个或更少)固定数量的元素，可以使用一个排序网络。这似乎是较不为人所知的算法之一。如果必须反复排序小的元素集，也许是在硬件中实现的话，这将是非常有用的。