如何对大部分排序的数组进行排序

以下内容 site 在常用排序算法之间进行比较-似乎插入排序在集合接近排序时获胜。

“当我坐在键盘前,给一个冒泡的端口编码时,他们笑了…”

但说真的:起泡是近距离的,但不是完全的。BubbleSort重复地向一个方向移动,因此,如果在数组的顶端附近有一个低调的值,它和比较站点“Bubbles”一直向上移动,则数据项需要多次主循环的迭代才能向下冒泡以对抗当前值。这几乎是最坏的情况,这对冒泡是灾难性的。

但是有一种对气泡的精炼,有时被称为 电梯 鸡尾酒式,气泡在其中交替运动:一个向上,一个向下,重复。这允许单个元素在一次传递中移动很长的距离(实际上是2次传递),并且传递的数量与需要移动的元素的数量成比例。对于少数未排序的元素,这可以接近效率。

我相信在一般情况下,Marek答案中的第二个链接会更快。泡沫的优势/ 电梯 鸡尾酒是如此简单,它几乎是万无一失的,而且不是很多工作。

如果它已经被排序到如此高的程度,并且不完全排序的元素离它们的正确位置不远,那么这可能是少数几个 bubblesort 是有用的。

谷歌给出了一个 lot of results 为此,例如,本文概述了如何实现这一目标的各种方法: http://home.tiac.net/~cri/2004/ksort.html

把它们放在一个数组中。你不想搞到一个40K的链接列表。

有一个非常狭隘的案例 CocktailSort (向两个方向起泡)。但这取决于1%的未排序意味着什么。如果有一些元素被替换,但靠近它们的目标位置,它可能会起作用。

但是 InsertionSort 或 ShellSort 几乎总是会赢。即使在理论上鸡尾酒会更好的情况下,差异也会很小。所以他们是更安全的赌注。

与大多数此类问题一样,答案是“那取决于……”。您是否关心排序是否稳定,也就是说,如果键相等的元素在排序后保持其原始相对顺序?你只关心原始速度吗?实现的简单性重要吗?内存消耗有关系吗?

我个人会的 总是 选择一个稳定的排序算法,因为我愿意为我认为是“合理”的行为牺牲一些原始速度,而非稳定的排序常常是“不合理”的。所以我倾向于使用合并排序算法,它快速且相当简单,但它确实使用了额外的内存。合并排序的另一个优点是,如果数据已经排序,那么它的复杂性是O(n),所以对于几乎排序的数据,它应该接近O(n)。

YMMV。

性能是否关键(由分析器验证)?否则,只需使用框架/langauge的默认排序(可能是quicksort)。它会表现得很好。