哪种sortingalgorithm最适合大多数sorting的数据?

哪种sortingalgorithm对大多数sorting数据最有效?

基于观看GIFanimation的高度科学的方法,我会说插入和泡泡sorting是很好的候选人。

只有几个项目=>插入sorting

项目大多已​​经sorting=>插入sorting

关注最坏情况=> HEAP SORT

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

物品是从密集的宇宙=>桶式sorting

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

timsort

Timsort是“一种自适应的,稳定的,自然的合并”,“ 在多种部分有序的arrays上超自然的performance (less于lg(N!)比较所需,less至N-1)”。 Python的内置sort()已经使用了这个algorithm一段时间,显然有很好的结果。 它专门devise用于检测和利用input中部分sorting的子序列,这通常发生在真实数据集中。 在现实世界中,通常情况下,比较比在列表中交换项目要昂贵得多,因为通常只是交换指针,这经常使得timsort成为一个很好的select。 然而,如果你知道你的比较总是非常便宜(例如编写一个玩具程序来对32位整数进行sorting),那么其他algorithm可能会performance得更好。 利用timsort最简单的方法当然是使用Python,但是由于Python是开源的,你也可以借用代码。 或者,上面的描述包含足够多的细节来编写自己的实现。

插入sorting与以下行为:

  1. 对于时隙1..n每个元素k ,首先检查是否el[k] >= el[k-1] 。 如果是,则转到下一个元素。 (显然跳过第一个元素。)
  2. 如果不是,则使用元素1..k-1二进制search来确定插入位置,然后扫描元素。 (只有当k>T ,你才可以做到这一点,其中T是某个阈值,小k就是过度杀伤。

这种方法进行比较的次数最less。

尝试内省sorting。 http://en.wikipedia.org/wiki/Introsort

这是基于快速sorting的,但它避免了快速sorting对几乎sorting的列表造成的最坏情况行为。

诀窍是,这种sortingalgorithm检测到快速sorting进入最坏情况模式并切换到堆或合并sorting的情况。 几乎sorting的分区是由一些不可感知的分区方法检测到的,小分区是通过插入sorting来处理的。

您将获得所有主要sortingalgorithm中最好的代码,从而使代码更加复杂。 而且无论您的数据如何,您都可以确定您永远不会遇到最坏的情况。

如果你是一个C ++程序员,请检查你的std :: sortalgorithm。 它可能已经在内部使用了内省的sorting。

插入或shellsorting!

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

与插入sorting相比,它的优势在于,当数据根本没有sorting时,它不会恢复到O(n ^ 2)行为,所以在使用它之前不需要确定数据是部分sorting的。

它的缺点是它需要的splay树结构额外的空间开销,以及构build和销毁splay树所需的时间。 但是,根据数据的大小和预期分类的数量,开销可能会增加速度。

在Software – Practice&Experience 上发表了一篇关于splaysort的论文 。

Dijkstra的smoothsort对已sorting的数据很有帮助。 这是一个heapsort变种,以O(n lg n)最坏情况和O(n)最好情况运行。 我写了一个algorithm的分析 ,以防你好奇它是如何工作的。

自然mergesort是另一个非常好的 – 这是一个自下而上的mergesort变种,通过将input视为多个不同sorting范围的连接,然后使用合并algorithm将它们连接在一起。 你重复这个过程,直到所有的input范围被sorting。 如果数据已经sorting并且O(n lg n)最差,这将在O(n)时间内运行。 这是非常优雅的,虽然在实践中它不如Timsort或smoothsort其他适应性sorting。

插入sorting需要花费时间O(n +反转次数)。

反演是一个对(i, j) ,使得i < j && a[i] > a[j] 。 那是一个无序的对。

“几乎sorting”的一个措施就是反演的次数—人们可以把“几乎sorting的数据”作为反转次数很less的数据。 如果知道反转的数量是线性的(例如,你刚刚添加了O(1)元素到一个sorting列表),插入sorting需要O(n)时间。

如果元素已经被sorting或者只有很less的元素,那么对于插入sorting来说,这将是一个完美的用例。

正如其他人所说,要小心天真的Quicksort – 可以在sorting或近似sorting的数据上具有O(N ^ 2)性能。 尽pipe如此,用适当的枢轴selectalgorithm(无论是随机的还是三中位数 – 请参阅select快速sorting的枢轴),Quicksort仍然可以运作。

一般来说,select插入sortingalgorithm的难度在于决定数据何时足够乱序以至Quicksort真的会更快。

我不会假装在这里有所有的答案,因为我认为得到实际答案可能需要对algorithm进行编码,并将其与代表性数据样本进行比较。 但是我整个晚上都在想这个问题,到目前为止,我发生了什么事情,还有一些猜测是什么在哪里最好。

设N为总数,M为乱序数。

泡泡sorting将不得不让2 * M + 1通过所有N项。 如果M很小(0,1,2?),我认为这将很难被击败。

如果M小(比N小),插入sorting将有很好的平均性能。 但是,除非我没有看到一个技巧,否则将会有非常糟糕的performance。 (对吗?如果顺序中的最后一项出现在第一位,那么您必须插入每一个项目,据我所知,这将杀死性能。)我猜这里有一个更可靠的sortingalgorithm情况,但我不知道它是什么。

如果M比N大(比N大),那么内省的sorting几乎肯定是最好的。

所有这些例外:如果事实上事先知道哪些元素是未sorting的,那么最好的办法就是将这些项目拉出来,用反省式sorting,然后将两个sorting后的列表合并成一个sorting列表。 如果你能很快弄清楚哪些项目不合适,这也是一个很好的通用解决scheme – 但我还没有find一个简单的方法来做到这一点。

进一步的想法(一夜之间):如果M + 1 <N / M,那么你可以扫描列表寻找sorting的N / M行的运行,然后扩展在任一方向运行找出订购商品。 这将至多需要2N比较。 然后,您可以sorting未sorting的项目,并在两个列表上进行sorting合并。 总的比较应该less于像4N + M log2(M)这样的东西,我想这将打败任何非专门的分类程序。 (更进一步的想法是:这比我想象的更复杂,但我仍然认为这是合理的。)

这个问题的另一个解释是可能有许多无序项目,但是它们非常接近它们应该在列表中的位置。 (想象一下,从一个sorting的列表开始,将每一个其他项目换成其后的项目)。在这种情况下,我认为泡泡sortingperformance非常好 – 我认为通过次数将与一个项目最远的地方成比例是。 插入sorting将效果不佳,因为每个不按顺序的项目都会触发插入。 我怀疑内省sorting或类似的东西也会运作良好。

如果您需要特定的sortingalgorithm,数据结构或任何有上述链接的实现,我可以向您推荐CodePlex上出色的“数据结构和algorithm”项目吗?

它将拥有你需要的一切,而不需要重新发明轮子。

只是我的一点盐。

在这个答案中,这个用于这个目的的sortingalgorithm的好集合似乎缺乏Gnome Sort ,这也是合适的,可能需要最less的实现努力。

插入sorting是最好的情况O(n)在sorting的input。 大部分sorting的input都非常接近(比快速sorting更好)。

思考尝试堆。 我相信这是O(n lg n)中最一致的。

泡泡分类(或更安全的双向泡泡分类)对于大多数已sorting的列表来说可能是理想的select,但是我敢打赌,梳理分类(具有更低的初始间隔尺寸)会比列表更快一些,相当完美的sorting。 梳子sorting降级到泡沫sorting。

那么这取决于用例。 如果你知道哪些元素发生了变化,就我而言,删除和插入将是最好的情况。

泡沫sorting绝对是赢家下一个雷达将是插入sorting。

远离QuickSort – 对预先sorting的数据非常低效。 插入sorting通过移动尽可能less的值来处理几乎sorting的数据。