如何在最快的时间内对几乎排序的数组进行排序？(JAVA)

Question

如何在最快的时间内对几乎排序的数组进行排序？(JAVA)

Ale*_*rev 13 java sorting algorithm performance smoothsort

我有一个几乎但没有完全排序的值数组,其中一些值被置换(例如,50在100000中).如何最有效地排序？(性能在这里绝对至关重要,应该比O(N)更快).

我知道smoothsort,但我找不到Java实现.有谁知道它是否已经实施？或者我可以用于此任务而不是smoothsort？

Answer 1

And*_*ich 19

实际上,Wikipedia包含smoothsort的Java实现.你可以在这里找到它:

http://en.wikipedia.org/wiki/Smoothsort.

Answer 2

Dig*_*oss 10

鸡尾酒排序

如果您想要一个易于实现的简单算法,您可以进行鸡尾酒排序.它几乎可以很好地处理几乎排序的输入.

Answer 3

Roe*_*ler 7

正如Botz3000所说,你不能比O(N)更快地执行这样的操作.任何算法的最基本元素是在阵列中找到那些乱序的条目.这需要O(N),甚至在你弄清楚如何处理它们之前.

如果"无序"元素的数量确实低于元素总数的数量级,则可以使用以下算法(假设链接列表):

查找所有无序项目并从原始列表中提取到单独的列表O(N)
结果是两个列表:排序列表和短提取列表
对于每个提取的元素,将它们插入到排序列表中.那将是每个的O(log(N)),total是O(Xlog(N)),其中X是提取的元素的数量.如果X相对于N非常小,则最终得到总O(N).

实际上并不难以证明.您可以通过计算x/n - > 0时xlog(n)的限制来证明它. (2认同)
@Rax:是的,你可以找到它们,但可能会发生*所谓的"无序"元素的数量也恰好是O(N)*.当你看它时,即使阵列的数量较少.考虑[1,5,10,2,3,4,5,6,7,8,9,10,11].暴力算法将无序调用元素2到10.这对后来的步骤没有任何意义. (2认同)

Answer 4

tem*_*def 5

有很多好的算法.

Smoothsort是我个人的最爱...... 如果你好奇为什么它如此有效,我实际上在这里完成了所有的数学运算.

已经排序的数据的一个相当好的算法是自然mergesort,它是mergesort的自下而上版本,通过将输入视为一系列已排序的子范围,然后在合并相邻排序范围的范围内进行多次传递.如果数据已经排序(因为它可以检测到只有一个排序范围),它会在O(n)时间运行,而在最坏的情况下,它会运行O(n lg n).如果数据是"块排序的",该算法可以很好地工作; 也就是说,它由许多排列在一起的排序块组成.

直接插入排序绝对适用于大多数排序数据,但在很多输入上可能会非常糟糕地退化.一些非常好的排序(如introsort)实际上使用插入排序的这个属性来对输入执行"清理步骤".

归档时间：	16 年前
查看次数：	10978 次
最近记录：	10 年，7 月前