问题标签 [smoothsort]

我有一个值数组，几乎但不是完全排序，有一些值被替换（例如，100000 中有 50 个）。如何最有效地排序？（性能在这里绝对至关重要，应该比 O(N) 快得多）。

我知道smoothsort，但我找不到Java 实现。有谁知道它是否已经实施？或者我可以用什么来代替smoothsort？

从维基百科上阅读这篇关于排序算法的文章，smoothsort 似乎是最好的排序算法。它在所有类别中都具有最佳性能：最佳、平均和最差。在任何类别中都没有什么能比得上它。它还具有恒定的内存要求。唯一的缺点是不稳定。

它在内存方面胜过 timsort，在最坏情况下的性能和内存方面都胜过 quicksort。

但我从来没有听说过smoothsort。没有人提到它，而且大多数讨论似乎都围绕着其他排序算法。

这是为什么？

根据这篇文章，树的根在位置 L(k) - 1。Ltk-1 子树的根在位置 L(k - 1) - 1。Ltk-2 子树的根在位置 L(k) - 2。

有人可以帮我理解这个吗？我正在尝试实现平滑排序。