我有值的数组，这几乎是，但并不完全排序，流离失所几个值（比如，50 100000）。如何最有效地排序呢？ （性能绝对在这里至关重要，应方式比O（N）更快）。

I have an array of values which is almost, but not quite sorted, with a few values displaced (say, 50 in 100000). How to sort it most efficiently? (performance is absolutely crucial here and should be way faster than O(N)).

我知道smoothsort，但我找不到Java实现。有谁知道它是否已经实现？或者，我可以用什么完成这个任务，而不是smoothsort？

I know about smoothsort, but I can't find Java implementation. Does anyone know whether it is already implemented? Or what I can use for this task instead of smoothsort?

推荐答案

事实上，维基百科中包含的Java实现smoothsort的。你可以在这里找到它：

Actually, the Wikipedia contains a Java implementation of smoothsort. You can find it here:

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