何时使用合并排序以及何时使用快速排序？

Question

用于合并排序的维基百科文章.

在维基百科文章的快速排序.

两篇文章都具有出色的可视化.

两者都具有n*log(n)复杂度.

显然,数据的分布将影响排序的速度.我的猜测是,由于比较可以快速比较任何两个值,无论它们的扩散如何,数据值的范围都无关紧要.

更重要的是,应该考虑关于排序的横向分布(x方向)(去除幅度).

如果测试数据具有一定程度的排序,那么需要考虑的一个好的测试用例......

Answer 1

它通常取决于所涉及的数据结构.快速排序通常是最快的,但它不保证O(n*log(n)); 有退化的情况,它变成O(n ^ 2).堆排序是通常的选择; 它保证O(n*log(n)),无论初始顺序如何,但它具有更高的常数因子.它通常在您需要时间的硬上限时使用.一些更新的算法使用快速排序,但尝试识别它何时开始退化,然后切换到堆排序.当数据结构不支持随机访问时使用合并排序,因为它适用于纯顺序访问(转发迭代器,而不是随机访问迭代器).std::list<>::sort例如,它被用于.它还广泛用于外部排序,与顺序访问相比,随机访问可能非常非常昂贵.(当排序不适合内存的文件时,您可以将其分解为适合内存的块,使用快速排序对它们进行排序,将每个文件写入文件,然后合并对生成的文件进行排序.)

Answer 2

在处理链表时,Mergesort更快.这是因为在合并列表时可以很容易地更改指针.它只需要通过列表一次(O(n)).

Quicksort的就地算法需要移动(交换)数据.虽然这对于内存数据集非常有效,但如果您的数据集不适合内存,则可能会更加昂贵.结果将是大量的I/O.

现在,发生了很多并行化.并行化Mergesort比Quicksort(就地)更简单.如果不使用就地算法,那么quicksort的空间复杂度是O(n),它与mergesort相同.

因此,为了概括,快速排序对于适合内存的数据集可能更有效.对于更大的东西,最好使用mergesort.

使用mergesort而不是quicksort的另一般时间是数据非常相似(即,不接近统一).Quicksort依赖于使用数据透视表.在所有值都相似的情况下,快速排序击中O(n ^ 2)的最坏情况.如果数据的值非常相似,则更可能选择不良的数据透视导致非常不平衡的分区,从而导致O(n ^ 2)运行时.最直接的例子是列表中的所有值是否相同.

Answer 3

有一种真实的排序算法 - 称为Timsort--它利用了在野外遇到的数据经常被部分排序的想法.

该算法源自合并排序和插入排序,并在CPython,Java 7和Android中使用.

有关更多详细信息,请参阅Wikipedia文章.

Answer 4

在这两者中,当您需要稳定排序时使用合并排序.您可以使用修改后的快速排序(例如introsort),因为它往往更快,并且使用更少的内存.

Hoare描述的普通老式Quicksort对性能特殊情况非常敏感Theta(n^2),因此通常需要修改版本.这就是数据分发的来源,因为合并排序没有坏的情况.一旦你开始修改quicksort,你可以继续进行各种不同的调整,而introsort是更有效的调整之一.它可以即时检测它是否处于杀手状态,如果是,则切换到heapsort.

实际上,Hoare最基本的Quicksort在已经排序的数据中失败最差,所以你的"好的测试用例"具有一定程度的排序会将其杀死到某种程度.不过,这个事实只是为了好奇,因为它只需要一个非常小的调整就可以避免这种情况,没有什么比一直到内省更复杂.因此,甚至懒得分析被排序数据杀死的版本也很简单.

在实践中,在C++中你通常使用std::stable_sort和std::sort,而不是过于担心确切的算法.

Answer 5

Java 6 及更早版本使用归并排序作为排序算法，而 C# 使用 QuickSort 作为排序算法。

即使它们都是 O(nlogn)，QuickSort 的性能也比归并排序好。QuickSort 的常数比归并排序小。