从阅读此文章从维基百科上的排序算法,它似乎是smoothsort是最好的排序算法存在.它在所有类别中都有最佳表现:最佳,平均和最差.在任何类别中都没有什么比这更好的了.它还具有恒定的内存要求.唯一的缺点是它不稳定.
它在内存中击败了timsort,并且它在最坏情况下的性能和内存方面都快速进入.
但我从来没有听说过smoothsort.没有人提到它,大多数讨论似乎围绕其他排序算法.
这是为什么？
我有一个几乎但没有完全排序的值数组,其中一些值被置换(例如,50在100000中).如何最有效地排序？(性能在这里绝对至关重要,应该比O(N)更快).
我知道smoothsort,但我找不到Java实现.有谁知道它是否已经实施？或者我可以用于此任务而不是smoothsort？