java - 如何有效地对 int 数组进行排序

Question

我有一个整数数组

int array[] = ...

我可以使用

对其进行排序

Arrays.sort(array);

但 Arrays.sort 使用快速排序，这有时会导致 O(n^2) 复杂度。我有一个想法将它转换为 List 然后对其进行排序(使用合并排序，因此上限是 O(n log n))，但缺点是它创建了很多对象，因为从 int 到 Integer 的装箱。

我的第三种方法是:

array = Arrays.stream(array).sorted().toArray();

我只在 IntStream 上操作，但不幸的是文档中没有提到复杂性。

我一直在寻找类似的问题，但我只找到了这个 Big-O complexity of java.util.stream.Stream<T>.sorted()这根本没有帮助，因为有两个不同的答案(第一个当然是部分错误的，因为 Arrays.sort 并不总是 O(n log n))。第二个呢？我还没有找到证据。

Answer 1

你应该调查Heapsort ，虽然稍微慢一点，但它保证了 O(n Log n)。 Quicksort vs heapsort

还有课本解释here .