哪种排序算法对大多数排序的数据最有效？
graphics
问问题
139594 次
20 回答
273
基于观看动画 gif的高度科学的方法，我会说插入和冒泡排序是很好的选择。
于 2008-10-20T21:41:23.967 回答
121
只有几项 => 插入排序
项目大多已经排序 => INSERTION SORT
担心最坏的情况=> HEAP SORT
对良好的平均情况结果感兴趣 => QUICKSORT
物品来自密集的宇宙 => BUCKET SORT
希望编写尽可能少的代码 => 插入排序
于 2010-11-25T10:40:10.237 回答
31
时间排序
Timsort是“一种自适应的、稳定的、自然的归并排序”，具有“在多种偏序数组上的超自然性能（少于 lg(N!) 比较所需，并且少至 N-1）”。Python的内置sort()使用这个算法有一段时间了，显然效果不错。它专门用于检测和利用输入中的部分排序子序列，这些子序列通常出现在真实数据集中。在现实世界中，比较通常比交换列表中的项目要昂贵得多，因为通常只是交换指针，这通常使 timsort 成为一个很好的选择。但是，如果您知道您的比较总是非常便宜（例如，编写一个玩具程序来对 32 位整数进行排序），那么存在其他可能表现更好的算法。利用 timsort 最简单的方法当然是使用 Python，但由于 Python 是开源的，您也可以借用代码。或者，上面的描述包含足够的细节来编写您自己的实现。
于 2008-10-21T04:17:11.297 回答
20
具有以下行为的插入排序：
k对于slot中的每个元素1..n，首先检查是否el[k] >= el[k-1]. 如果是这样，请转到下一个元素。（显然跳过第一个元素。）- 如果不是，请在元素中使用二分搜索
1..k-1来确定插入位置，然后将元素扫过。k>T（只有在某个阈值在哪里时，您才可以这样做T；如果阈值很小k，那就是矫枉过正了。）
此方法进行的比较次数最少。
于 2008-10-20T21:48:19.757 回答
11
尝试内省排序。http://en.wikipedia.org/wiki/Introsort
它是基于快速排序的，但它避免了快速排序对几乎排序列表的最坏情况行为。
诀窍是这种排序算法检测到快速排序进入最坏情况模式并切换到堆或合并排序的情况。通过一些非天真的分区方法检测接近排序的分区，并使用插入排序处理小分区。
以更多代码和复杂性为代价，您可以获得所有主要排序算法中最好的。而且您可以确保无论您的数据看起来如何，都不会遇到最坏的情况。
如果您是 C++ 程序员，请检查您的 std::sort 算法。它可能已经在内部使用内省排序。
于 2008-10-20T22:29:37.973 回答
7
Splaysort是一种基于splay 树（一种自适应二叉树）的模糊排序方法。Splaysort 不仅适用于部分排序的数据，也适用于部分反向排序的数据，或者实际上任何具有任何类型预先存在顺序的数据。在一般情况下是 O(nlogn)，在数据以某种方式（正向、反向、风琴管等）排序的情况下是 O(n)。
与插入排序相比，它的最大优势在于，当数据根本没有排序时，它不会恢复为 O(n^2) 行为，因此您无需绝对确定数据在使用前已部分排序.
它的缺点是它需要的展开树结构的额外空间开销，以及构建和销毁展开树所需的时间。但是，根据您期望的数据大小和预排序数量，开销对于提高速度可能是值得的。
一篇关于 splaysort的论文发表在 Software--Practice & Experience 上。
于 2008-10-21T04:02:28.113 回答
5
Dijkstra 的smoothsort 是对已排序数据的一种很好的排序。这是一个堆排序变体，在 O(n lg n) 最坏情况和 O(n) 最佳情况下运行。我写了一个算法分析，以防你好奇它是如何工作的。
自然归并排序是另一个非常好的方法——它是一种自下而上的归并排序变体，它通过将输入视为多个不同排序范围的串联，然后使用合并算法将它们连接在一起。您重复此过程，直到对所有输入范围进行排序。如果数据已经排序并且 O(n lg n) 最坏情况，这将在 O(n) 时间内运行。它非常优雅，尽管在实践中它不如 Timsort 或 Smoothsort 等其他自适应排序。
于 2010-11-09T21:11:59.230 回答
5
插入或外壳排序！
于 2008-10-20T21:43:01.733 回答
4
如果元素已经排序或者只有很少的元素，这将是插入排序的完美用例！
于 2012-10-29T11:42:27.667 回答
3
插入排序需要时间 O(n + 反转次数)。
反转是一对(i, j)这样i < j && a[i] > a[j]。也就是乱序对。
“几乎排序”的一种衡量标准是反转的数量——可以将“几乎排序的数据”表示具有很少反转的数据。如果知道反转次数是线性的（例如，您刚刚将 O(1) 个元素附加到排序列表中），则插入排序需要 O(n) 时间。
于 2009-06-02T21:33:25.247 回答
2
正如其他人所说，小心天真的快速排序 - 它可以在排序或几乎排序的数据上具有 O(N^2) 性能。尽管如此，使用适当的算法选择枢轴（随机或三的中位数 - 请参阅为快速排序选择一个枢轴），快速排序仍然可以正常工作。
一般来说，选择诸如插入排序之类的算法的困难在于确定数据何时足够乱序，以便快速排序确实更快。
于 2008-10-20T22:00:40.513 回答
2
我不会假装在这里拥有所有答案，因为我认为获得实际答案可能需要对算法进行编码并根据代表性数据样本对其进行分析。但是我整个晚上都在思考这个问题，这是我到目前为止发生的事情，以及一些关于什么地方最有效的猜测。
令 N 为项目总数，M 为无序数。
冒泡排序必须使类似 2*M+1 的东西通过所有 N 个项目。如果 M 非常小（0、1、2？），我认为这将很难被击败。
如果 M 很小（比如小于 log N），则插入排序将具有很好的平均性能。但是，除非有我没有看到的技巧，否则它的最坏情况下的性能会很差。（对吧？如果订单中的最后一项排在第一位，那么您必须插入每一项，据我所知，这会影响性能。）我猜有一个更可靠的排序算法可以解决这个问题案例，但我不知道它是什么。
如果 M 更大（比如等于或大于 log N），内省排序几乎肯定是最好的。
所有这一切的例外：如果您实际上提前知道哪些元素未排序，那么您最好的选择是将这些项目拉出，使用内省排序对它们进行排序，然后将两个排序列表合并为一个排序列表。如果您可以快速找出哪些项目出现故障，这也是一个很好的通用解决方案——但我无法找到一种简单的方法来做到这一点。
进一步的想法（一夜之间）：如果 M+1 < N/M，那么您可以扫描列表以查找已排序的连续 N/M 的运行，然后在任一方向展开该运行以查找出-订购物品。这最多需要 2N 次比较。然后，您可以对未排序的项目进行排序，并对两个列表进行排序合并。总比较应该小于 4N+M log2(M) 之类的东西，我认为这将击败任何非专业排序程序。（进一步思考：这比我想象的要棘手，但我仍然认为这是合理的。）
该问题的另一种解释是，可能有许多乱序项，但它们非常接近它们应该在列表中的位置。（想象一下从一个排序列表开始，然后将所有其他项目与它之后的项目交换。）在这种情况下，我认为冒泡排序表现得非常好——我认为通过的次数将与最不合适的项目成正比是。插入排序效果不佳，因为每个乱序项都会触发插入。我怀疑内省排序或类似的东西也会很好用。
于 2008-10-21T03:23:24.277 回答
1
答案中用于此目的的排序算法的这个不错的集合似乎缺少Gnome Sort，这也是合适的，并且可能需要最少的实现工作。
于 2011-10-15T13:26:38.500 回答
1
于 2008-10-21T12:10:06.053 回答
0
插入排序是排序输入的最佳情况 O(n)。它非常接近大多数排序的输入（比快速排序更好）。
于 2008-10-20T21:44:33.930 回答
0
冒泡排序（或者更安全的双向冒泡排序）可能是大多数排序列表的理想选择，尽管我敢打赌，调整后的梳状排序（初始间隙大小要小得多）在列表不存在时会更快一些t 完全排序。梳排序降级为冒泡排序。
于 2008-10-21T12:59:40.620 回答
0
冒泡排序绝对是赢家 雷达上的下一个将是插入排序。
于 2012-09-21T11:48:43.437 回答
0
好吧，这取决于用例。如果您知道更改了哪些元素，就我而言，删除和插入将是最好的情况。
于 2012-08-16T19:52:14.770 回答
-1
思考尝试堆。我相信这是最一致的 O(n lg n) 排序。
于 2008-10-20T21:49:36.290 回答
-2
远离 QuickSort - 它对预排序数据的效率非常低。插入排序通过移动尽可能少的值来很好地处理几乎排序的数据。
于 2008-10-20T21:44:12.730 回答