logo标签列表

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

c#.netalgorithmsorting
4
我有一个像这样的数组：
1,2,3,5,6,4 它已经排序了99%，并且有40K个元素。
我可以将它们放入数组、列表、链表等数据结构中，
但是我不知道最快的排序方法！
你在用哪种编程语言？ - Andy E
@andy，为什么要关心编程语言？ - atv
我认为Dror的答案更准确，应该被接受。对于几乎排序好的数组，插入排序是最好的选择，因为每次插入步骤所需的比较次数较少。 - atv
就我个人而言，我同意。我仍然认为应该考虑使用冒泡排序（和/或电梯排序），因为它们很简单。 - philsquared
可能是which-sort-algorithm-works-best-on-mostly-sorted-data的重复问题。 - nawfal
显示剩余3条评论
7个回答
21

以下网站比较了常见的排序算法 - 似乎在集合接近排序时，插入排序会胜出。

@behrooz 点击每个单独的图像以查看它们的功能。 - James
看起来冒泡排序并没有比插入排序差太多，但是如果你有一个在相反端的单个值，那将会对结果产生很大影响。 - Wim
1
是的，对于冒泡排序来说，乱序元素距离它们目标位置的距离有多远将是致命的，特别是在处理大型集合时。 - philsquared
最近弗拉基米尔·亚罗斯拉夫斯基提出了一种名为“双轴快速排序”的新算法，详情请见：http://gdtoolbox.com/DualPivotQuicksort.pdf。 - JasDev
6

"当我坐在键盘前编写冒泡排序时，他们都笑了起来..."

但说真的：冒泡排序虽然接近，但并不完美。冒泡排序一直向一个方向移动，所以如果数组顶端附近有一个低值，并且比较位置一直"冒泡"上升，那么数据项对当前的下降需要经过许多次主循环迭代。这几乎是最坏的情况，对于冒泡排序来说是灾难性的。

但是有一种改进的冒泡排序，有时被称为电梯鸡尾酒排序，其中气泡交替地向两个方向移动：一次向上，一次向下，重复进行。这使得单个元素可以在单次遍历（或实际上是2次遍历）中移动很长的距离，而遍历次数与需要移动的元素数量成比例。对于少量未排序的元素，这可以接近效率。

我认为对于一般情况，Marek回答中的第二个链接会更快。冒泡/电梯鸡尾酒排序的优点在于它非常简单，几乎是傻瓜式的，而且工作量不大。

交替变体通常被称为鸡尾酒排序。http://en.wikipedia.org/wiki/Cocktail_sort - H H
1
谢谢你提供CocktailSort的指针。这正是我所需要的。(我有一堆精灵，需要按Y顺序排序。这个算法足够高效，我可以在每一帧调用它，而不会感觉到速度上的影响。) - Joe Strout
3
如果已经排序到这么高的程度，而未完全排序的元素离其正确位置不远，那么这可能是冒泡排序有用的少数情况之一。
2
我还没有完全理解第二个链接中的“ksort”是如何工作的，但看起来有人花了很多心思。可能是一个不错的选择，点赞。 - Carl Smotricz
1

将它们放入一个数组中。你不想去处理一个有40k个链接的链表。

鸡尾酒排序（两向冒泡排序）有一个非常狭窄的用例。但这取决于那1%未排序到底意味着什么。如果有一些元素被错位，但接近它们的目标位置，它可能会起作用。

但是插入排序或希尔排序几乎总是能够胜出。即使在鸡尾酒排序理论上更好的情况下，差异也很小。所以它们是（更）安全的选择。

0

和大多数这类问题一样，答案是“那要看情况……”。你在意排序是否稳定，即键值相等的元素在排序后是否保留其原始相对顺序？你只关心原始速度吗？实现的简单性重要吗？内存消耗是否重要？

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

你的情况可能有所不同。

这是一个存储在内存缓存中以供离线使用的SQL主键列，因此我不需要稳定排序。我的输出是一个数组，因此它可以使用大小为N或更大的数组。 - Behrooz
0

性能是否关键（由分析器验证）？否则，只需使用您的框架/语言的默认排序（可能是快速排序）。它将表现良好。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接