如何在最快时间内对近似排序的数组进行排序?(Java)
我有一个值数量的值,几乎是但并非完全分类,有几个值流离失所(例如,100000中的50个值).如何最有效地对其进行分类? (在这里的性能绝对至关重要,应该比O(n)更快). 我知道Smoothsort,但找不到Java实现.有人知道它是否已经实施吗?或我可以将其用于此任务而不是Smoothsort? 解决方案 实际上,Wikipedia包含Smoothsort的Java实现.您可以在这里找到它: http://en.wikipedia.org/wiki/wiki/smoothsort . 其他解决方案 鸡尾酒排序 如果您想要一种易于实现的简单算法,则可以做一个鸡尾酒.它将在几乎分量的输入上很好地工作. 其他解决方案 如Botz3000所述,您不能比O(n)更快地执行此类操作.任何算法的最基本元素都是在数组中找到不顺序的条目.这需要o(n),甚至在您弄清楚如何处理它们之前. 如果确实,"排序"元素的数量是元素总数低的数量级,则可以使用以下算法(假
10 2024-01-22
编程技术问答社区
为什么smoothsort不是更常见?
从读取从维基百科的文章在排序算法上,似乎是shimplysort是最好的排序算法.它在所有类别中具有最佳性能:最佳,平均和最差.没有什么能在任何类别中击败它.它还具有持续的内存要求.唯一的缺点是它不稳定. 它在内存中击败了timsort,它在最坏情况和内存中击败了Quicksort. 但我从未听过关于Speedssort.没有人曾经提到过,大多数讨论似乎都围绕了其他分类算法. 为什么? 解决方案 Big-O表现非常适合发布论文,但在现实世界中,我们也需要看待常量. Quicksort一直是不稳定,就地的选择算法,因为我们可以非常有效地实现其内循环,并且非常缓存友好.即使您可以像Quicksort一样高效地实现SpileSort的内循环,或者几乎可以高效地实现,您可能会发现其缓存未命中率使其变慢. 我们通过花费更多的努力来缓解Quicksort的最坏情况性能,选择良好的枢轴(减少病理案件的数量)和检测病理情况.查找 Introsort . Introsort
1398 2022-07-17
编程技术问答社区