哪种排序算法最适合大多数排序数据？

哪种排序算法最适合大多数排序数据？

1> Tom Ritter..：

---

基于高度科学的观看GIF动画的方法,我会说插入和泡泡排序是很好的候选人.

---

jjnguy,这是完全错误的.我认为你需要重新学习你的算法课程.在几乎排序的数据(它的自适应情况)上,它是O(N).但是,通过数据需要2次传递,而插入只需要1对于近似排序的数据,这使得Insertion成为赢家.泡泡仍然很好

---

顺便说一句,这是一个很好的联系,荣誉和+1

---

冒泡排序太可怕了.它总是O(n ^ 2).至少从你的答案中取出它是正确的请.

---

当我尝试时,这个链接被打破了.试试这个:http://www.sorting-algorithms.com/

---

如果您的数据几乎没有排序,性能会严重下降.我个人还是不会用它.

---

该链接应该在每个排序问题中.谢谢!

2> Jiaji Li..：

---

只有几个项目=> INSERTION SORT

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

关注最坏情况=> HEAP SORT

对平均案例结果感兴趣=> QUICKSORT

物品来自密集的宇宙=> BUCKET SORT

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

---

您应该添加"数据已按其他标准排序=> MERGE SORT"

3> zaphod..：

---

timsort

Timsort是"一种适应性,稳定,自然的融合",具有" 在多种部分有序阵列上的超自然表现(需要少于1g(N!)的比较,以及少于N-1)".Python的内置sort()已经使用这个算法一段时间了,显然效果很好.它专门用于检测和利用输入中部分排序的子序列,这些子序列通常出现在真实数据集中.在现实世界中通常情况下,比较比在列表中交换项目要昂贵得多,因为通常只是交换指针,这通常使得timsort成为一个很好的选择.但是,如果您知道您的比较总是非常便宜(例如,编写玩具程序以对32位整数进行排序),则存在其他可能表现更好的算法.利用timsort的最简单方法当然是使用Python,但由于Python是开源的,你也可以借用代码.或者,上面的描述包含足够的细节来编写您自己的实现.

---

log(n!)是Ο(n*log(n))因此它不是"超自然的".

---

@JF Sebastian:在几乎排序的数组上,timsort比`lg(n!)`比较快得多,一直到'O(n)`!| @behrooz:没有比较排序可以有一个比'O(n log n)`更好的平均情况,而`lg(n!)`是'O(n log n)`.因此,timsort的最坏情况渐渐地没有比任何其他比较类型差.此外,其最佳情况优于或等于任何其他比较排序.

---

Timsort在最糟糕的情况下仍然是O(nlogn),但它的好例子非常令人愉快.这是一个比较,有一些图表:http://stromberg.dnsalias.org/~strombrg/sort-comparison/请注意,Cython中的timsort并不像Python在C中内置的timsort那么快.

4> Jason Cohen..：

---

插入排序具有以下行为:

对于k插槽中的每个元素1..n,首先检查是否el[k] >= el[k-1].如果是这样,请转到下一个元素.(显然跳过第一个元素.)

如果没有,请在元素中使用二进制搜索1..k-1来确定插入位置,然后将元素划过.(只有k>T在T某个阈值的位置时才可以这样做;小的时候k这可能是过度的.)

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

5> Nils Pipenbr..：

---

尝试内省排序.http://en.wikipedia.org/wiki/Introsort

它基于quicksort,但它避免了quicksort对近乎排序的列表的最坏情况行为.

诀窍在于此排序算法检测快速排序进入最坏情况模式并切换到堆或合并排序的情况.通过一些非naiive分区方法检测几乎排序的分区,并使用插入排序处理小分区.

您可以获得所有主要排序算法中最好的,以获得更多代码和复杂性的成本.无论您的数据如何,您都可以确定自己永远不会遇到最坏的情况.

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

6> TimB..：

---

Splaysort是一种基于splay树的模糊排序方法,splay树是一种自适应二叉树.Splaysort不仅适用于部分排序的数据,还适用于部分反向排序的数据,或者实际上任何具有任何预先存在的顺序的数据.在一般情况下是O(nlogn),在数据以某种方式(正向,反向,器官管道等)排序的情况下是O(n).

与插入排序相比,它的优势在于,当数据完全没有排序时,它不会恢复为O(n ^ 2)行为,所以在使用数据之前,您不需要绝对确定数据是否已经部分排序.

它的缺点是它需要的splay树结构的额外空间开销,以及构建和销毁splay树所需的时间.但是,根据您预期的数据大小和预先排序的数量,对于速度的提高,开销可能是值得的.

关于splaysort的论文发表在Software - Practice&Experience中.

7> ninesided..：

---

插入或shell排序!

8> templatetype..：

---

Dijkstra的smoothsort对已排序的数据非常有用。这是一个堆排序变体，以O（n lg n）最坏情况和O（n）最佳情况运行。如果您好奇它是如何工作的，我就对算法进行了分析。

Natural mergesort是另一个非常好的解决方案-它是一个自底向上的mergesort变体，其工作方式是将输入视为多个不同排序范围的串联，然后使用merge算法将它们连接在一起。您重复此过程，直到对所有输入范围进行了排序。如果数据已经排序，则运行时间为O（n），最坏情况为O（n lg n）。它非常优雅，尽管实际上它不如Timsort或smoothsort等其他自适应类型好。