哪种排序算法对大部分已排序的数据最有效？

小开

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

小开

插入或外壳排序！

小开

远离快速排序-它对预先排序的数据非常低效。插入排序通过移动尽可能少的值来很好地处理几乎已排序的数据。

小开

插入排序是已排序输入的最佳情况 O (n)。而且它非常接近大多数已排序的输入(比快速排序好)。

小开

具有以下行为的插入排序:

对于插槽 1..n中的每个元素 k，首先检查 el[k] >= el[k-1]是否。如果是这样，请转到下一个元素。(显然要跳过第一个元素。)
如果没有，则在元素 1..k-1中使用二进制搜索来确定插入位置，然后将元素移过。(只有当 k>T中的 T是某个阈值时才可以这样做; 对于小的 k，这样做有些过分。)

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

小开

Ponder 尝试堆。我相信它是 O (n lg n)类型中最一致的。

小开

正如其他人所说的那样，要小心幼稚的快速排序——它可能在排序或接近排序的数据上具有 O (N ^ 2)性能。尽管如此，如果有一个适当的枢轴选择算法(随机或中位数为3的为快速排序选择支点) ，快速排序仍然可以正常工作。

一般来说，选择诸如插入排序之类的算法的困难在于决定何时数据足够混乱以至于 Quicksort 真的会更快。

小开

试试 Introsort

它是基于快速排序的，但它避免了快速排序对于几乎排序的列表所具有的最坏情况行为。

诀窍在于，这种排序算法可以检测快速排序进入最坏情况模式并切换到堆或合并排序的情况。通过一些非纯粹分区方法检测几乎排序的分区，并使用插入排序处理较小的分区。

您可以在所有主要排序算法中获得最好的排序算法，而代价是更多的代码和复杂性。无论你的数据看起来如何，你可以确定你永远不会遇到最坏的情况。

如果你是一个 c + + 程序员，检查你的 std: : sort 算法，它可能已经在内部使用了 Introsort。

小开

我不打算假装这里有所有的答案，因为我认为要得到实际的答案可能需要编写算法，并根据具有代表性的数据样本对它们进行分析。但是我整个晚上都在思考这个问题，以下是到目前为止我想到的，以及一些关于什么在哪里最有效的猜测。

设 N 为项目总数，M 为无序数。

冒泡排序必须使类似2 * M + 1的内容通过所有 N 个项。如果 M 很小(0,1,2?)，我认为这将是非常难以打败。

如果 M 很小(比如小于 log N) ，插入排序将具有很好的平均性能。然而，除非有一个我没有看到的技巧，它将有非常糟糕的最坏情况下的表现。(对吧？如果顺序中的最后一个项目排在第一位，那么您必须插入每一个项目，在我看来，这将扼杀性能。)我猜这个案子还有更可靠的排序算法但我不知道是什么。

如果 m 大于(比如说等于或大于对数 n) ，那么 Introsort 几乎肯定是最好的。

例外情况: 如果你事先知道哪些元素是未排序的，那么你最好的选择就是把这些元素拉出来，用 Introsort 对它们进行排序，然后把两个已排序的列表合并到一个已排序的列表中。如果您能够快速找出哪些项目出了问题，那么这也将是一个很好的通用解决方案——但是我还没有找到一个简单的方法来做到这一点。

进一步的想法(一夜之间) : 如果 M + 1 < N/M，那么你可以扫描列表，在一行中寻找 N/M 的运行排序，然后向任何一个方向展开，找到无序的项目。这最多需要2N 次比较。然后可以对未排序的项进行排序，并对两个列表执行排序后的合并。总的比较应该小于4N + M log2(M) ，我认为这将击败任何非专门的排序例程。(更进一步的想法是: 这比我想象的要棘手，但我仍然认为这是合理可能的。)

对这个问题的另一种解释是，可能存在许多无序的项目，但它们非常接近它们应该在列表中的位置。(想象一下，从一个已排序的列表开始，将每个其他项目与后面的项目交换。)在这种情况下，我认为气泡排序表现得非常好——我认为传递的次数将与一个项目最不合适的位置成正比。插入排序效果很差，因为每个无序项都会触发插入。我想 Introsort 之类的东西也会很有用。

小开

Splaysort 是一种基于种树的模糊排序方法，种树是一种自适应二叉树。Splaysort 不仅适用于部分排序的数据，还适用于部分反向排序的数据，或者任何具有任何预先存在顺序的数据。在一般情况下是 O (nlogn) ，在以某种方式(正向、反向、风琴管道等)对数据进行排序的情况下是 O (n)。

与插入排序相比，它的巨大优势在于，当数据根本没有排序时，它不会恢复为 O (n ^ 2)行为，所以在使用数据之前，不需要绝对确定数据已经部分排序。

它的缺点是它需要扩展树结构的额外空间开销，以及构建和销毁扩展树所需的时间。但是，取决于数据的大小和预先排序的数量，您期望的开销可能是值得的，因为速度的增加。

关于 playsort 的论文出版于《软件——实践与经验》。

小开

Timsort

Timsort 是“一种适应性强、稳定、自然的合并排序”，具有“强大”的超自然性能所需的部分有序数组种类 (小于 lg (N!)比较，以及只有 N-1)”。Python 的内置 sort()使用这种算法已经有一段时间了，显然效果不错。它专门用于检测和利用输入中部分排序的子序列，这些子序列通常出现在实际数据集中。在现实世界中，比较通常比交换列表中的项要昂贵得多，因为通常只是交换指针，这通常使 timsort 成为一个很好的选择。然而，如果您知道您的比较总是非常便宜(例如，编写一个玩具程序来排序32位整数) ，其他算法可能会表现得更好。利用 timsort 的最简单方法当然是使用 Python，但是由于 Python 是开源的，所以您也可以借用这些代码。或者，上面的描述包含了足够多的细节来编写您自己的实现。

小开

如果您需要具体的实现排序算法，数据结构或任何有链接到上述，我可以向您推荐优秀的 “数据结构和算法”项目的 CodePlex？

不需要重造轮子就可以满足你的一切需求。

我只是有点怀疑。

小开

冒泡排序(或者更安全的双向冒泡排序)可能是大多数排序列表的理想选择，不过我敢打赌，如果列表排序不是那么完美的话，经过调整的梳状排序(初始间隔大小要小得多)会更快一些。梳状排序退化为气泡排序。

小开

插入排序需要时间 O (n + 倒排次数)。

反转是一对 (i, j)，这样的 i < j && a[i] > a[j]。也就是说，一个无序对。

衡量“几乎排序”的一个指标是反转的次数——可以用“几乎排序的数据”来表示几乎没有反转的数据。如果知道倒排的次数是线性的(例如，您刚刚将 O (1)元素附加到排序列表中) ，则插入排序需要 O (n)时间。

小开

Dijkstra 的平滑排序是对已经排序的数据的一种很好的排序。它是在 O (n lg n)最坏情况和 O (n)最好情况下运行的堆排序变体。我是算法的写了一篇分析报告如果你好奇它是如何工作的。

自然合并排序是另一个非常好的方法——它是一个自底向上的合并排序变体，它将输入视为多个不同排序范围的连接，然后使用合并算法将它们连接在一起。重复这个过程，直到所有的输入范围都被排序。如果数据已经排序，并且 O (n lg n)最坏情况下，这将在 O (n)时间内运行。它非常优雅，尽管在实践中它不如 Timsort 或平滑排序等其他自适应排序。

小开

只有几个项目 = > INSERTION 排序

项目大多已经排序 = > INSERTION SORT

关注最坏情况下的场景 = > HEAP SORT

对一个好的平均情况结果感兴趣 = > QUICKSORT

项是从稠密的宇宙中抽取的 = > 桶排序

希望编写尽可能少的代码 = > INSERTION SORT

小开

这个很好的排序算法集合在答案中用于这个目的，似乎缺少侏儒排序，这也是合适的，并且可能需要最少的实现工作。

小开

这取决于用例。如果您知道更改了哪些元素，那么就我而言，删除和插入将是最好的情况。

小开

泡泡排序肯定是赢家雷达上的下一个应该是插入排序。

小开

如果元素已经排序或只有少量元素, 这将是一个完美的插入排序用例！