合并、堆和快速排序在哪些情况下有用？
In which cases are merge-, heap- and quicksort useful?
我正在研究什么时候哪种排序算法更快更有效。从我到目前为止所读到的有关插入排序等排序算法的内容来看，当您使用小型数组时以及当它们几乎被排序或排序时，它非常有效，因为运行时平均 O(N).
堆排序有点棘手并且使用优先级队列。它将事物插入到优先级队列中并删除它们。使用堆时，最好将列表的顺序或任何顺序颠倒过来。合并排序需要稳定性并且在链表上效果最好。
所以我的问题是，这些排序算法在什么时候比其他算法更有用？因为可以说我可以使用任何一个，对吧？我会选择哪种算法，基于什么情况，例如遇到这样的场景。
假设我有一个包含很少元素的小数组，并且它几乎已排序。
包含 200 万个元素的大列表，并且已排序。您只想更改几个元素。
一个非常大的数组，其中的元素占用了大量内存。
一个包含几十万个元素的逆向排序列表。说我要换几千的位置。
Say I have a small array with few elements and it's nearly sorted.
对于小数组的第一种情况，不需要使用合并排序或快速排序等高级排序算法。冒泡排序、选择排序或插入排序在这里是最好的（考虑递归等的开销）。由于它几乎已排序，因此插入排序将表现最佳，因为它的最佳情况是 O(N)。
Big list with 2 million elements and they're sorted. You want to change say a few elements only.
很大程度上取决于什么元素。它们是原始类型吗？如果是这样，那么比较它们就不是时间上的大问题。如果（让我们假设我们正在使用 Java）它们是自己创建的对象，那么比较它们可能会非常耗时。比较 Java 中的长字符串可能非常耗时。
元素较多，排除前面三种简单的算法（插入排序、冒泡排序、选择排序）。您想使用合并排序或快速排序。
合并排序比快速排序比较少，但在元素周围移动更多。然而，在这种特殊情况下，我会选择合并排序，因为如果我们不小心选择了排序顺序中的最小值或最大值，那么在如此大的集合中选择一个枢轴值真的会花费你很多很多时间。
A really big array with elements that are taking up big memory.
同样，什么元素？假设您几乎没有内存，Quicksort 是您的选择。递归调用的开销可能很昂贵，但在 Java 中，这不是什么大问题 在这种情况下 。
A list with a few hundred thousand elements that come in reverse sorting. Say I want to change position of a couple of thousand.
没什么大惊小怪的，但是元素的类型是什么？这个很棘手。在这里，我们还需要考虑其他因素。我真的不能仅仅根据给定的信息就说一个比另一个好。
选择正确的排序算法有点复杂。我们使用什么数据结构？如果我们有一个数组，索引很快，所以我们需要考虑其他因素。如果我们使用链接结构，也许我们应该尽可能避免 "indexing-based" 算法。我给出的这些例子远非规则。它们更像是指南。选择一个好的排序算法是根据具体情况而定的。希望这至少能有所帮助。
我正在研究什么时候哪种排序算法更快更有效。从我到目前为止所读到的有关插入排序等排序算法的内容来看，当您使用小型数组时以及当它们几乎被排序或排序时，它非常有效，因为运行时平均 O(N).
堆排序有点棘手并且使用优先级队列。它将事物插入到优先级队列中并删除它们。使用堆时，最好将列表的顺序或任何顺序颠倒过来。合并排序需要稳定性并且在链表上效果最好。
所以我的问题是，这些排序算法在什么时候比其他算法更有用？因为可以说我可以使用任何一个，对吧？我会选择哪种算法，基于什么情况，例如遇到这样的场景。
假设我有一个包含很少元素的小数组，并且它几乎已排序。
包含 200 万个元素的大列表，并且已排序。您只想更改几个元素。
一个非常大的数组，其中的元素占用了大量内存。
一个包含几十万个元素的逆向排序列表。说我要换几千的位置。
Say I have a small array with few elements and it's nearly sorted.
对于小数组的第一种情况，不需要使用合并排序或快速排序等高级排序算法。冒泡排序、选择排序或插入排序在这里是最好的（考虑递归等的开销）。由于它几乎已排序，因此插入排序将表现最佳，因为它的最佳情况是 O(N)。
Big list with 2 million elements and they're sorted. You want to change say a few elements only.
很大程度上取决于什么元素。它们是原始类型吗？如果是这样，那么比较它们就不是时间上的大问题。如果（让我们假设我们正在使用 Java）它们是自己创建的对象，那么比较它们可能会非常耗时。比较 Java 中的长字符串可能非常耗时。
元素较多，排除前面三种简单的算法（插入排序、冒泡排序、选择排序）。您想使用合并排序或快速排序。
合并排序比快速排序比较少，但在元素周围移动更多。然而，在这种特殊情况下，我会选择合并排序，因为如果我们不小心选择了排序顺序中的最小值或最大值，那么在如此大的集合中选择一个枢轴值真的会花费你很多很多时间。
A really big array with elements that are taking up big memory.
同样，什么元素？假设您几乎没有内存，Quicksort 是您的选择。递归调用的开销可能很昂贵，但在 Java 中，这不是什么大问题 在这种情况下 。
A list with a few hundred thousand elements that come in reverse sorting. Say I want to change position of a couple of thousand.
没什么大惊小怪的，但是元素的类型是什么？这个很棘手。在这里，我们还需要考虑其他因素。我真的不能仅仅根据给定的信息就说一个比另一个好。
选择正确的排序算法有点复杂。我们使用什么数据结构？如果我们有一个数组，索引很快，所以我们需要考虑其他因素。如果我们使用链接结构，也许我们应该尽可能避免 "indexing-based" 算法。我给出的这些例子远非规则。它们更像是指南。选择一个好的排序算法是根据具体情况而定的。希望这至少能有所帮助。