logo标签列表

哪种排序算法在大部分已经有序的数据上表现最佳？

algorithmsorting
188

哪种排序算法在大部分已排序数据上表现最好？

从缺乏上下文来猜测 - 你是在询问内存排序，而没有要求将中间结果溢出到磁盘吗？ - Jonathan Leffler
3
根据这些动画（http://www.sorting-algorithms.com/nearly-sorted-initial-order），插入排序在大部分已排序的数据上表现最佳。 - dopple
20个回答
278

基于观看动画gif的高度科学方法，我认为插入排序和冒泡排序是不错的选择。

19
顺便说一下，那是一个非常好的链接，赞一个加一。 - ninesided
5
冒泡排序很差劲，它的时间复杂度始终为O(n^2)。请至少将此内容从你的答案中删除以使其正确。 - jjnguy
84
jjnguy，那是完全错误的。我认为你需要重新学习算法课程。在近乎有序的数据上（即自适应情况），它的时间复杂度为O（N）。然而，它需要对数据进行两次遍历，而插入排序仅需要一次遍历。这使得插入排序成为更好的选择。但冒泡排序仍然是不错的。 - mmcdole
3
如果数据没有接近排序，性能会急剧下降。但就我个人而言，我仍然不会使用它。 - Blorgbeard
5
当我尝试访问那个链接时，发现它已经失效了。请尝试使用这个链接代替：http://www.sorting-algorithms.com/。 - Michael La Voie
显示剩余10条评论
128

仅有少量项目 => 插入排序

项目大多已排序 => 插入排序

担心最坏情况 => 堆排序

对良好的平均情况结果感兴趣 => 快速排序

项目来自密集的范围内 => 桶排序

希望尽可能少的编写代码 => 插入排序

1
这正是我一直在寻找的答案类型，我阅读了很多书籍，但似乎没有找到特定情况下选择算法的清晰解释，您能否详细说明一下或提供一个链接，以便我可以更深入地了解？谢谢。 - systemdebt
13
你应该添加“数据已经按照另一个标准排序=>归并排序”。 - Jim Hunziker
@JimHunziker，你能否提供一个链接，让我找到一个利用你提到的模式的归并排序实现吗？或者说，普通的归并排序就可以在没有任何改变的情况下做到这一点吗？ - python_user
2
由于归并排序是一种稳定排序算法，新排序中具有相同键的项目将按照旧排序保持排序。例如，如果您有一个按名字排序的列表，然后按姓氏进行归并排序，则姓氏为Smith的人将按其名字保持排序。这适用于所有归并排序的实现。 - Jim Hunziker
33

timsort

Timsort 是一种“自适应、稳定、自然合并排序”，在许多部分有序的数组中表现出“超自然的性能（需要少于 lg(N!) 的比较，最少 N-1 次)”。Python内置的sort()算法已经使用此算法相当长一段时间，并取得了良好的效果。它专门设计用于检测和利用输入中部分排序的子序列，这通常在真实数据集中经常发生。在现实世界中，往往比交换列表中的项目要昂贵得多的是比较操作，因为通常只需交换指针，这往往使timsort成为一个很好的选择。但是，如果您知道您的比较操作总是非常便宜的（例如编写一个程序来对32位整数进行排序），则可能存在其他算法，其性能可能更好。当然，利用timsort最简单的方法是使用Python，但由于Python是开源的，您也可以借用其代码。或者，上述描述包含足够的细节，可以编写您自己的实现。

21
log(n!) 是 Ο(n*log(n))，因此它并不是“超自然”的。 - jfs
这是Java实现，适用于JDK7：http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java - Tim
log(n!) 不够快。http://www.wolframalpha.com/input/?i=plot[log(N!),{N,0,1000}] - Behrooz
9
@J.F. Sebastian: 在几乎有序的数组上，timsort比使用“lg(n!)”次比较快得多，一直到O(n)为止！@behrooz: 任何比较排序的平均情况都无法优于O(n log n)，而lg(n!)是O(n log n)。因此，timsort的最坏情况渐近复杂度不会比任何其他比较排序更差。此外，它的最佳情况比任何其他比较排序都要好或相等。 - Artelius
3
Timsort在最坏情况下仍然是O(nlogn)，但它的优化情况非常好。这里有一个比较，附带一些图表：http://stromberg.dnsalias.org/~strombrg/sort-comparison/请注意，Cython中的Timsort并不像Python内置的C版本Timsort那样快。 - user1277476
20

使用如下行为的插入排序：

  1. 对于插槽 1..n 中的每个元素 k，首先检查 el[k] >= el[k-1] 是否成立。如果成立，则继续下一个元素。（显然跳过第一个元素）
  2. 如果不成立，在元素 1..k-1 中使用二分查找来确定插入位置，然后将元素向右移动。（如果 k>T，其中 T 是某个阈值，则可能只需要这样做；对于小的 k 这是过度工作）。

该方法进行的比较次数最少。

我认为如果未排序元素的数量非常少（比如一个或两个），冒泡排序可能会更快，但总体而言，这似乎是最好的解决方案。 - Sol
因为步骤1，对于已经排序的任何元素，都只需要进行一次比较和零次数据移动，这显然是最好的情况。步骤2是你可以改进的步骤，但是气泡排序将会移动相同数量的元素并且可能有更多的比较，这取决于你的实现方式。 - Jason Cohen
实际上，经过进一步的思考，我认为冒泡排序比我想象的要强大。这实际上是一个相当棘手的问题。例如，如果您采取列表完全排序的情况，除了应该是最后一个元素的元素是第一个之外，冒泡排序将远远优于您所描述的内容。 - Sol
我尝试实现这个，但是二分查找并没有太大的改进，因为你仍然需要移动整个块来插入元素。所以，你得到的不是2xrange，而是range + logb(range)。 - this
11

尝试使用内省排序（Introspective Sort） http://en.wikipedia.org/wiki/Introsort

该算法基于快速排序（Quicksort），但它避免了快速排序在几乎有序列表上出现最坏情况的行为。

这个排序算法的技巧是检测快速排序进入最坏情况模式的情况，并切换到堆排序或归并排序。一些非朴素的分区方法用于检测几乎有序的分区，并使用插入排序处理小分区。

你可以通过付出更多代码和复杂性的代价，获得所有主要排序算法的优点。无论数据如何，您都可以确保不会遇到最坏情况。

如果你是C++程序员，请检查std::sort算法。它可能在内部已经使用内省排序。

7

Splaysort 是一种基于splay trees（一种自适应二叉树）的鲜为人知的排序方法。Splaysort 不仅适用于部分排序数据，还适用于部分反向排序数据或者任何已有某种预定顺序的数据。它在一般情况下是O(nlogn)，在数据以某种方式排序（正向、反向、管风琴等）的情况下是O(n)。

与插入排序相比，它最大的优点是当数据没有排序时不会退化为O(n^2)行为，因此您不需要绝对确定数据是部分排序的才能使用它。

它的缺点是需要额外的空间开销来存储所需的splay tree结构，以及构建和销毁splay tree所需的时间。但是，根据您期望的数据大小和预排序程度，这种开销可能值得增加速度。

一篇关于Splaysort的论文已经在《软件--实践与经验》杂志上发表。

5
迪科斯彻的平滑排序算法是在已排序数据上运行良好的排序算法。它是堆排序的一种变体，最坏情况下运行时间为O(n lg n)，最好情况下为O(n)。如果您想了解其工作原理，可以看看我对该算法 的分析。
自然合并排序是另一个非常不错的算法-它是一种自底向上的合并排序变体，通过将输入视为多个不同排序范围的连接来工作，然后使用合并算法将它们连接在一起。重复这个过程直到所有输入范围都排序完成。如果数据已经排序，则其运行时间为O(n)，最坏情况下为O(n lg n)。尽管非常优雅，但实际上它没有Timsort或smoothsort等其他自适应排序算法好用。
平滑排序算法相对于其他排序算法的运行时常数是多少？（即对于相同数据，平滑排序算法的运行时长 / 插入排序算法的运行时长） - Arne Babenhauserheide
5
插入排序或希尔排序！
4

如果元素已经排序或者只有很少的元素，插入排序将是一个完美的使用案例！

3

插入排序的时间复杂度为O (n + 逆序对数量)。

逆序对是一对“ (i，j)”，其中 i < j 且 a [i]> a [j] 。也就是说，这是一个无序的配对。

衡量“几乎有序”的一种方法是逆序对的数量——“几乎有序数据”可以理解为具有较少逆序对的数据。例如，如果人们知道逆序对的数量是线性的（例如，您只向排序列表中添加了 O(1) 个元素），则插入排序的时间复杂度为O(n)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接